接雨水

Leetcode Link: 42. 接雨水 - 力扣（LeetCode）

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

解法一

思路： 单调栈，没有单调栈的思路可以先做柱状图中最大的矩形，然后做最大矩形，再过来思考本题。

本题的单调栈一直保持小的数字在栈顶，如果遇到大的数字，需要进行处理。我们同样保持栈里的元素是列表，遇到等于号不是新建入栈，而是append到栈顶的列表里。

首先，一个简单的思路是 遍历 height，

• 如果当前的 height[i] 比栈顶高度小，则直接 stack.append([i])
• 相等时需要`stack[-1].append (i)
• 如果当前的 height[i] 比栈顶高度大，则 pop 出来作为当前雨水掉落的底 bottom，然后以 min(height[stack[-1][0]], height[i])-height[bottom[0]] 作为当前这个位置为底的雨水池的高，以 i-stack[-1][0]+1 为宽计算这部分的雨水的面积

这个思路大体正确，但是有几个细节问题和小坑

1. 如果栈空或者栈只有一个元素，那么无论遇到什么高度都需要把这个位置入栈，而不用管其大小
   • 若栈空，则没什么说的，必需入栈
   • 若len(stack)==1，同时height[i]>height[stack[-1][0]]，此时雨水会从左边流下去，不能取出栈顶元素计算雨水的面积，但是为了不丢情况，需要append([i])
   • 若 len(stack)==1，同时 height[i]==height[stack[-1][0]]，此时雨水同样会从左边流下去，不能取出栈顶元素计算雨水的面积，我们同样需要 append([i])（其实这里也可以 stack[-1].append(i)，不过后面我们会有额外处理可以使这步的行为跟遇到大数字一样）
2. 假设此时新来一个元素，同时栈中有两个元素，并有 height[i]>height[stack[1][0]]，有下面几个情况
   • 栈里的两个元素高度递增，即有 height[i]>height[stack[1][0]]>height[stack[0][0]]，此时留不住雨水，会从左边流下去，但是我们不能忽略，必需要把这个位置入栈
   • 栈里的两个元素高度递减，即有 height[i]>height[stack[1][0]]<height[stack[0][0]]，此时可以留住雨水，正常处理
3. 从 2 中我们知道，当栈中有两元素高度递增的时候，处理起来会有一点复杂 (我们暂时先不讨论怎么处理)。我们知道，当遇到一个比栈顶元素高度大的位置时，栈顶会被弹出。推而广之，当有 3 个及以上元素时，也会由于弹出的操作导致 stack 前面一些元素变成递增的。 比如下图中，红色为当前遍历的位置高度，左侧123为栈里元素对应的高度。此时的操作是弹出3后计算3位置能储存的雨水。 然而，接下红色高度依然高于 2，按照一般想法，红色不能入栈，同时需要计算 2 位置储存的雨水。但是实际上 2 位置存不住雨水，会从左侧流下去。综上，显然此时又回到了 2 问题中的第一种情况，即无论如何必需 append 进来。因此我们知道了

   当栈中现有的高度一直是递增的时候，我们遇到了更大的高度，也必须 append 进来

4. 如何处理 2，3。 显然，2，3 情况的出现是由于栈里并不是一直都是递减的，那么我们只需要在每次遍历到某个位置之前，将栈处理成递减的形式即可。这就解释了在情况 1 中，当栈里只有一个元素时，即使遇到了相等的高度，我们也可以入栈一个新的元素 append([i]) ：因为在这里，我们会将栈处理成严格递减，相等的高度前一个会被 pop 掉，这不会影响雨水面积计算，如图。 左侧为栈 (1, 2, 3, 4)，按照高度递减处理后变成 (3, 4)，遇到当前位置 (红色)，由于保留了离当前位置最近的同时还高的位置，就不会有错误计算

至此，我们注意上面提到的几个小坑和问题，就可以写代码了。

题解：

class Solution:
    def trap(self, height: List[int]) -> int:
        stack = [] # 这里不用哨兵
        res = 0
 
        for i in range(len(height)):
            # 将栈里处理成严格递减
            while(len(stack)>=2 and height[stack[1][0]] >= height[stack[0][0]]):
                stack.pop(0)
            # 栈里元素个数大于等于2个，则需要考虑留不留的下雨水
            while(len(stack) > 1 and height[i] > height[stack[-1][0]]):
                bottom = stack.pop()
                #      (高)*(宽)
                res += (min(height[stack[-1][0]], height[i])-height[bottom[0]])*(i-stack[-1][-1]-1)
            # 栈里元素只有一个的时候，只能入栈，对应情况1
            if len(stack) <= 1:
                stack.append([i])
                continue
            # 到这里，可以保证栈里元素个数一定大于等于2，且不可能当前高度比栈顶高度小
            if height[i] < height[stack[-1][0]]:
                stack.append([i])
            if height[i] == height[stack[-1][0]]:
                stack[-1].append(i)
        
        return res

解法二

思路：

题解：

解法三

思路：

题解：

启发和联系