题目描述

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

思路题解

单调栈

https://leetcode-cn.com/problems/trapping-rain-water/solution/trapping-rain-water-by-ikaruga/

class Solution:
    def trap(self, height: List[int]) -> int:
        def cal(l,cur,r):
            h=min(height[l],height[r])
            return (abs(l-r)-1)*(h-height[cur])
        i,n,ans,down=0,len(height),0,[]
        while i+1<n and height[i]<=height[i+1]:
            i+=1
        down.append(i)
        i+=1
        while i<n:
            if height[i]>height[down[-1]]:
                while len(down)>0 and height[down[-1]]<height[i]:
                    cur=down.pop()
                    if len(down)>0:
                        ans+=cal(down[-1],cur,i)
            down.append(i)
            i+=1
        return ans

dp

https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode-solution-tuvc/
看了答案不得不说一句，妙啊

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

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode-solution-tuvc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

双指针

https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode-solution-tuvc/

链接第三种方法，属于将dp改进了一下，后续可以再做一次