407. Trapping Rain Water II

解題說明

C++ 解法

複雜度分析

虛擬碼

Function trapRainWater(heightMap):
  m = rows, n = cols
  If m < 3 or n < 3: return 0

  // Step 1: Initialize min-heap with all border cells
  minHeap = empty min-heap
  visited[m][n] = all false
  For each border cell (r, c):
    Push (heightMap[r][c], r, c) into minHeap
    Mark visited[r][c] = true

  // Step 2: BFS from minimum boundary outward
  water = 0
  While minHeap not empty:
    (h, r, c) = pop minimum from minHeap
    For each neighbor (nr, nc) of (r, c):
      If out of bounds or already visited: continue
      Mark visited[nr][nc] = true
      If heightMap[nr][nc] < h:
        water += h - heightMap[nr][nc]   // can trap water
        Push (h, nr, nc) into minHeap     // effective height is h after filling
      Else:
        Push (heightMap[nr][nc], nr, nc) into minHeap

  Return water

其他解法

延伸思考