. 빗물 가두기 II

407. 제2저수지

난이도: 어려움

주제: 배열, 너비 우선 검색, 힙(우선순위 큐), 행렬

2D 고도 지도에서 각 셀의 높이를 나타내는 m x n 정수 행렬 heightMap이 주어지면 비가 내린 후 축적할 수 있는 물의 양을 반환합니다.

예 1:

• 입력: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3 ,2,3,1]]
• 출력: 4
• 설명: 비가 온 후 블록 사이에 물이 갇히게 됩니다.
  • 각각 1유닛과 3유닛의 물을 담는 두 개의 작은 수영장이 있습니다.
  • 절약된 물의 양은 총 4개입니다.

예 2:

• 입력: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3 ],[3,2,2,2,3],[3,3,3,3,3]]
• 출력: 10

제약조건:

• m == heightMap.length
• n == heightMap[i].length
• 1
• 0

해결책:

'저수지 II' 문제는 2차원 고도 지도(행렬로 표시됨)에 비가 내린 후 쌓인 물의 양을 계산해야 하는 까다로운 계산 문제입니다. 이 문제는 고전적인 "저장소" 문제를 2차원으로 확장하여 모든 방향의 흐름을 고려해야 하기 때문에 솔루션을 더욱 복잡하게 만듭니다.

핵심사항

1. 행렬 표현: heightMap 행렬에는 각 셀의 고도가 포함됩니다.
2. 경계 제약: 물은 경계 셀 밖으로 흘러나올 수 없습니다.
3. 힙 데이터 구조: 최소 힙(우선순위 큐)은 수위를 동적으로 시뮬레이션하는 데 사용됩니다.
4. 방문 매트릭스: 반복적인 셀 방문을 피하기 위해 방문한 노드를 추적합니다.

방법

이 솔루션은 우선순위 큐(최소 힙)에 따라 진행되는 폭 우선 검색(BFS) 접근 방식을 활용합니다.

1. 모든 경계 셀을 최소 힙에 추가하고 방문한 것으로 표시합니다.
2. 높이가 증가하는 순서로 셀 처리:
   • 각 셀마다 이웃 셀에 물을 '비축'해 보세요.
   • 이웃 셀과 업데이트된 높이 값을 힙에 푸시합니다.
3. 현재 셀과 이웃 셀의 높이 차이를 기준으로 축적된 물의 양을 누적합니다.

계획

1. 초기화:

   • 행렬 크기와 극단적인 사례를 정의합니다.
   • 경계 셀의 최소 힙을 초기화합니다.
   • 방문 행렬을 만듭니다.

2. 테두리 셀 삽입:

   • 모든 경계 셀과 해당 높이 값을 힙에 푸시합니다.
   • 방문한 것으로 표시하세요.

3. BFS 순회:

   • 힙이 비어 있지 않으면 높이가 가장 작은 셀을 추출합니다.
   • 모든 이웃을 확인하고 물 보유량을 계산하세요.
     • 이웃이 낮을수록 높이 차이로 인해 저장되는 물의 양이 늘어납니다.
     • 이웃의 키가 더 크면 이웃의 높이를 현재 셀의 높이로 업데이트하세요.
   • 이웃을 힙으로 푸시하고 방문한 것으로 표시합니다.

4. 반환 결과:

   • 누적된 물의 양은 누적된 빗물을 나타냅니다.

이 솔루션을 PHP로 구현해 보겠습니다. 407 Reservoir II

<?php
/**
 * @param Integer[][] $heightMap
 * @return Integer
 */
function trapRainWater($heightMap) {
    // ...  (解决方案代码将在此处) ...
}

// 示例用法
$heightMap1 = [[1, 4, 3, 1, 3, 2], [3, 2, 1, 3, 2, 4], [2, 3, 3, 2, 3, 1]];
$heightMap2 = [[3, 3, 3, 3, 3], [3, 2, 2, 2, 3], [3, 2, 1, 2, 3], [3, 2, 2, 2, 3], [3, 3, 3, 3, 3]];

echo trapRainWater($heightMap1) . "\n"; // 输出：4
echo trapRainWater($heightMap2) . "\n"; // 输出：10
?>

설명:

1. 경계 초기화:

   • 모든 경계 셀이 더미에 추가되어 컨테이너의 외벽을 형성합니다.

2. 힙 추출:

   • 물이 안쪽으로 흐르지 않고 바깥쪽으로만 흐르도록 높이가 가장 낮은 셀을 추출합니다.

3. 이웃 탐색:

   • 각 이웃에 대해:
     • 범위 내에 있고 액세스되지 않았는지 확인하세요.
     • 적어진 물의 양을 max(0, currentHeight - neighborHeight)로 계산합니다.
     • 업데이트된 이웃 높이를 힙에 푸시합니다.

4. 누적된 물:

   • 각 이웃의 물 저장량을 합계에 더합니다.

샘플 둘러보기

입력:

<code>$heightMap = [
    [1, 4, 3, 1, 3, 2],
    [3, 2, 1, 3, 2, 4],
    [2, 3, 3, 2, 3, 1]
];</code>

단계:

1. 테두리 셀:

   • 경계 셀과 해당 높이를 힙으로 푸시합니다.
     • 예: (0, 0, 1), (0, 1, 4) 등

2. 힙 순회:

   • 셀(0, 0, 1)(가장 낮은 높이)을 추출합니다.
   • 이웃을 확인하고 물 절약량 계산하기:
     • 이웃(1, 0)의 경우: 누적된 물 = max(0, 1 - 3) = 0.

3. 물 절약:

   • 모든 셀을 방문할 때까지 계속 처리합니다.
     • 총 물 절약량 = 4.

시간복잡도

1. 힙 작업:

   • 각 셀은 O(m n log(m * n))으로 한 번씩 힙에 푸시되고 팝됩니다.

2. 이웃 반복:

   • 각 셀에는 최대 4개의 이웃(O(m * n))이 있습니다.

전체적인 복잡성:

*O(m n log(m n))**

출력 예

<code>$heightMap = [
    [1, 4, 3, 1, 3, 2],
    [3, 2, 1, 3, 2, 4],
    [2, 3, 3, 2, 3, 1]
];
echo trapRainWater($heightMap); // 输出：4</code>

'저장소 II' 문제는 BFS와 결합된 우선순위 큐와 같은 고급 데이터 구조의 강력함을 보여줍니다. 2D 입면도에서 물의 흐름을 시뮬레이션함으로써 저장된 물의 총량을 효율적으로 계산할 수 있습니다. 로그 힙 작업으로 인해 이 솔루션은 대규모 행렬을 처리하는 데 최적입니다.

(전체 PHP 솔루션 코드는 여기에 포함되어야 합니다. 공간 제한으로 인해 여기에 제공할 수 없습니다. 전체 코드 구현은 원래 문제 설명의 ./solution.php 파일을 참조하세요.)

위 내용은 . 빗물 가두기 II의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!