42. Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/

solution

• 双指针/DP

# 纵向按列计算，每一列计算
class Solution:
    def trap(self, height: List[int]) -> int:
        max_left = [height[0]] * len(height)
        for i in range(1, len(height)):
            max_left[i] = max(max_left[i-1], height[i])

        max_right = [height[-1]] * len(height)
        for i in range(len(height)-2, -1, -1):
            max_right[i] = max(max_right[i+1], height[i])

        res = 0
        for i in range(len(height)):
            res += min(max_right[i], max_left[i]) - height[i]
        return res

时间复杂度：O(n) 空间复杂度：O(n)

• 单调栈

# 横向按行计算，单调栈：右边第一个比自己高的柱子出现时更新计算，此时才会出栈更新结果.
# 以自己为底，左右两边第一个比自己大的柱子，从而计算横向能够多少雨水

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = [0]
        result = 0
        for i in range(1, len(height)):
            # 当新的高度比之前大时，则进行结果更新
            while stack and height[i] > height[stack[-1]]:
                mid_idx = stack.pop()
                if stack:
                    # 关键是除了利用到了此时的高度height[i], 出栈的高度height[mid_idx]，还利用了留在栈里的高度作为左侧比他大的高度
                    # 雨水高度是 min(凹槽左侧高度, 凹槽右侧高度) - 凹槽底部高度, 按行计算计算的是高度差
                    h = min(height[stack[-1]], height[i]) - height[mid_idx]
                    # 雨水宽度是 凹槽右侧的下标 - 凹槽左侧的下标 - 1
                    w = i - stack[-1] - 1
                    result += h * w
            stack.append(i)
        return result

follow up

407. Trapping Rain Water II

# https://leetcode.com/problems/trapping-rain-water-ii/solutions/1138028/python3-visualization-bfs-solution-with-explanation/
# follow up: 778. Swim in Rising Water

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        if not heightMap or not heightMap[0]:
            return 0

        m, n = len(heightMap), len(heightMap[0])
        if m < 3 or n < 3:
            return 0

        heap = []
        for i in range(m):
            for j in range(n):
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:  # 边界
                    heapq.heappush(heap, (heightMap[i][j], i, j))
                    heightMap[i][j] = -1  # 修改值来省掉visited

        level = 0
        res = 0
        while heap:
            height, x, y = heapq.heappop(heap)
            level = max(height, level)

            for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
                new_x = x + dx
                new_y = y + dy
                if 0 <= new_x < m and 0 <= new_y < n and heightMap[new_x][new_y] != -1:
                    heapq.heappush(heap, (heightMap[new_x][new_y], new_x, new_y))
                    if heightMap[new_x][new_y] < level:
                        res += level - heightMap[new_x][new_y]

                    heightMap[new_x][new_y] = -1
        return res