0.总结

• 为了防止重复计算，求高度的时候 -height[top]是点睛之笔。而我的想法则是仅限于累积求出每次需要扣除的面积，但是放在这里使用的话，不好更新。
• 单调栈的性质便是：栈中的元素从某个角度来看是单调的。
• 博客来源： [email protected]

1.题目

2.思想

这道题还是挺精妙的，我知道用单调栈做，但是实现起来还是不容易。关键问题是，接到的雨水的性状是不规则的，怎么保证得到的雨水没有重复计算就是一个关键点。本题利用自身的一个矩形形状来扣除掉不需要计算的规则。具体如下：

• 栈中存放的数据规则：栈底到栈顶是从大到小。
• 每次计算雨水点数时，都存储了三个元素【确实只有至少长度为3的格子才有可能接到雨水】，分别是 height[left], height[top],height[cur] 其满足的条件是：
  height[left] >= height[top]，
  height[top] < height[cur]
  这个 top 可能就是需要扣除的多余面积。如下图：
  

因为这里的top是0，所以面积就是1。

这里因为top 是1，所以 min(cur,left) - top = 1 相当于只求了红框中面积，这样就避免了重复计算。

3.代码

class Solution:
    def trap(self, height: List[int]) -> int:
        height.append(0)
        res = 0
        stack = []
        stack.append(0) # 将0 位置的高度入栈
        for i in range(1,len(height)):
            # print(i,stack)
            # (1)如果当前位置的高度 小于 栈顶位置时，入栈。切记这里没有=
            if height[i] < height[stack[-1]]:
                stack.append(i)
            
            # 当前位置的高度大于等于栈顶位置，那么可以接雨水了。【等于的这个情况是为了消耗掉】
            else:
                if len(stack) <2 : # 如果当前栈中元素还不够，则继续入栈
                    stack.append(i) # 将当前这个节点放到栈中
                    continue
                else: # 已经超过2个元素了
                    while(len(stack)>=2
                        and height[i] >= height[stack[-1]] # 注意这个等于号，还是相当关键的
                        and height[stack[-2]] > height[stack[-1]]
                        ):
                        top = height[stack[-1]]
                        left = height[stack[-2]]
                        width = i - stack[-2] - 1 # 求出宽
                        cur_height = min(height[i],left) - top  # 求出高
                        cur_area = width * cur_height

                        res += cur_area
                        stack.pop() # 删除最后一个元素
                    stack.append(i) # 将当前这个节点放到栈中。这个也是比较重要的点
        return res       

下面这版代码ac不了，仅当作一个无效版本看看而已~

'''
思想
使用单调栈。具体来说：
（1）顺序遍历所有的数组，入栈规则如下：
a.如果当前比栈顶大，那么入栈（入栈的是数组下标）；
b.如果当前比栈顶小，那么计算当前这个黑块占得面积，后面计算的时候需要扣除掉
（2）轮流访问整个数组，直到结束。返回结果
'''
class Solution:
    def trap(self, height: List[int]) -> int:
        rain_num = 0 
        stack = [0] # stack 中存储的是下标。先放入第一个元素
        block = 0 # 遮挡住的面积
        for i in range(1,len(height)):
            # 如果不低于栈顶元素，那么这个时候就要考虑计算雨水点数了
            if height[i] >= height[stack[-1]]:                
                # 找到第一个高度不低于当前高度的位置
                while(height[i] > height[stack[-1]]): # 依次出栈
                    stack.pop() # 出栈
                
                length = i - stack[-1] - 1  # 计算长方形的长
                width = min(height[i],height[stack[-1]])
                cur_area = length * width - block # 
                rain_num += cur_area
                
                # 这里不是重置为0
                block +=  (i-stack[-1]) * height[i]
                stack.pop() # 移除栈顶
                stack.append(i)
                                
            else: # 较小值也要入栈
                stack.append(i)
                block += height[i]
        return rain_num