【困难】42. 接雨水-单调栈、动态规划、数学法、双指针

【题目】

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
1
2
3

【代码】数学法 图像填充切割

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        h1 = 0
        h2 = 0
        for i in range(len(height)):
            h1 = max(h1,height[i])
            h2 = max(h2,height[-i-1])
            ans = ans + h1 + h2 -height[i]
        return  ans - len(height)*h1
1
2
3
4
5
6
7
8
9
10

【方法2】
按照列进行遍历，每列可以接的雨水数=max(min(该列左侧最高高度，该列右侧最高高度)-当前列的高度，0)
解释：

• 当前列可以接的雨水数不会超过其左右两侧最高列的最低高度（短板效应）
• 当前列可以接的雨水数不会是负数，即：当前列超过左右两侧最高列的最低高度的情况

class Solution:
    def trap(self, height: List[int]) -> int:
        left=[]
        right=[]
        for i in range(len(height)):
            if left:left.append(max(height[i],left[-1]))
            else:left.append(height[i])
        height=height[::-1]
        for i in range(len(height)):
            if right:right.append(max(height[i],right[-1]))
            else:right.append(height[i])
        right=right[::-1]
        idx=0
        ans=0
        height=height[::-1]
        for l,r in zip(left,right):
            ans+=max(min(l,r)-height[idx],0)
            idx+=1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

【方法3】单调栈
使用单调栈记录从左到右，单调递减的边，因为只有递减的边才有可能存储水。
当遇到一个大于栈顶的边，则表明形成低洼可以存储水（因为栈顶前面的一条边是高于栈顶的，单调栈的特点，而当前的边也高于栈顶，所以形成了一个低洼）。

• while

1. 记录栈顶低洼处index，并弹出栈顶元素
2. 判断当前栈是否为空，即左侧还有没有边可以和当前边形式低洼
3. 如果当前栈为空，说明形成不了低洼，break跳出循环，否则执行下面操作
4. 计算当前边和栈顶边（原始的栈顶已经被弹出）形成的低洼处可以存储的水量
5. 将得到的水量计入全局变量ans（最后作为结果返回）

• 加入当前边进入单调栈（此时单调栈已经为空或者栈顶元素已经大于当前边）

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

class Solution:
    def trap(self, height: List[int]) -> int:
        ans=0
        stack=[]
        for idx,item in enumerate(height):
            while stack!=[] and item>height[stack[-1]]:
                top_index=stack[-1]
                stack.pop(-1)
                if stack==[]:
                    break
                h=min(height[stack[-1]],item)-height[top_index]
                w=idx-stack[-1]-1
                ans+=h*w
            stack.append(idx)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

【方法4】双指针
利用了木桶效应，木桶可以盛水量是由最短木块决定的

class Solution:
    def trap(self, height: List[int]) -> int:
        left,right=0,len(height)-1
        left_max,right_max,ans=0,0,0
        while left<right:
            if height[left]<height[right]:
                if height[left]>left_max:
                    left_max=height[left]
                else:
                    ans+=left_max-height[left]
                left+=1
            else:
                if height[right]>right_max:
                    right_max=height[right]
                else:
                    ans+=right_max-height[right]
                right-=1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18