42. Trapping Rain Water

接雨水问题
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
给定n个非负整数，每个整数代表高度图里面每个宽度为一的柱子。计算当下雨的时候，柱状中所表达的图形能接到多少雨水。

Example 1:

图例

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

• n == height.length
• 1 <= n <= 2 * 10<sup>4</sup>
• 0 <= height[i] <= 10<sup>5</sup>

题目分析

之前用动态规划找到过一道计算给定的木板长度围成的容器最大容积的题目，和这个类似（11.Container With Most Water）。当时的动态规划思路是，左右双指针，哪边的短就移动哪边的下标，向内收敛。并每次计算并比较找出最大容积。
我们尝试从这里找到类似的解决方案。我们遍历数组，找到比大于或者等于他的第一个长度的数组下标，计算其中容积。
以此类推。

class Solution:
    def cal_contain(self, height):
        h = height[0]
        ret = 0
        for i in range(1, len(height)):
            if h>height[i]:
                ret += h-height[i]
        return ret
            
    def trap(self, height: List[int]) -> int:
        left = 0
        right = 1
        l_h = len(height)
        ret = 0
        while left < l_h and right < l_h:
            while right < l_h and height[right]< height[left]:
                right += 1
            if right < l_h:
                ret += self.cal_contain(height[left:right])
                left = right
                right += 1
            
        left = 0
        right = 1
        height.reverse()
        while left < l_h and right < l_h:
            while right < l_h and height[right]<= height[left]:#注意这里用了小于等于。为了排除重复
                right += 1
            if right < l_h:
                ret += self.cal_contain(height[left:right])
                left = right
                right += 1

        return ret

两次循环。第一次从左边找，找左边是最高边，然后围成的容积。第二遍将列表转置，然后重复第一次的操作

答案解析

暴力法

算法：
从左至右遍历字符串。
然后每个节点分别向右和向左迭代。并计算可能的容积
将所有数值相加。
时间复杂度O(n^2)
空间复杂度O(1)

动态规划

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        
        n = len(height)
        leftMax = [height[0]] + [0] * (n - 1)
        for i in range(1, n):
            leftMax[i] = max(leftMax[i - 1], height[i])

        rightMax = [0] * (n - 1) + [height[n - 1]]
        for i in range(n - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i])

        ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))
        return ans

先分别用一次循环找出每个节点左边的最大值，和右边的最大值。
容积取决于两边最大值中的最小值。
时间复杂度O(n)
空间复杂度O(n)

单调栈

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        stack = list()
        n = len(height)
        
        for i, h in enumerate(height):
            while stack and h > height[stack[-1]]:
                top = stack.pop()
                if not stack:
                    break
                left = stack[-1]
                currWidth = i - left - 1
                currHeight = min(height[left], height[i]) - height[top]
                ans += currWidth * currHeight
            stack.append(i)
        
        return ans

双指针

降低空间复杂度的动态规划。利用双指针代替在动态规划中创建的左右列表

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        left, right = 0, len(height) - 1
        leftMax = rightMax = 0

        while left < right:
            leftMax = max(leftMax, height[left])
            rightMax = max(rightMax, height[right])
            if height[left] < height[right]:
                ans += leftMax - height[left]
                left += 1
            else:
                ans += rightMax - height[right]
                right -= 1
        
        return ans

总结

我的方法感觉也未尝不可，属于双指针和动态规划的中间版本。还有待更精进。