42. Trapping Rain Water

布满荆棘的人生 2022-05-06 04:00 125阅读 0赞

#### 42. Trapping Rain Water ####

参考：

*  [LeetCode Monotone Stack Summary 单调栈小结][LeetCode Monotone Stack Summary]

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.  
![在这里插入图片描述][70]

这道收集雨水的题目，非常的有意思。  
使用单调栈作为数据结构进行处理。  
单调栈的一大优势就是**线性的时间复杂度**，所有的元素只会进栈一次，而且一旦出栈后就不会再进来了。  
单调递增栈可以找到左起第一个比当前数字小的元素。  
单调递减栈可以找到左起第一个比当前数字大的元素。

*  分析：  
    给了边界的高度（黑色部分），让求能装的水量（蓝色部分）。 为啥能用单调栈来做呢？我们先来考虑一下，什么情况下可以装下水呢，是不是必须两边高，中间低呢？我们对低洼的地方感兴趣，就可以使用一个**单调递减栈**，将递减的边界存进去，一旦发现当前的数字大于栈顶元素了，那么就有可能会有能装水的地方产生。此时我们当前的数字是右边界，我们从栈中至少需要有两个数字，才能形成一个坑槽，先取出的那个最小的数字，就是坑槽的最低点，**再次取出的数字就是左边界**，我们比较左右边界，取其中较小的值为装水的边界，然后此高度减去水槽最低点的高度，乘以左右边界间的距离就是装水量了。由于需要知道左右边界的位置，所以我们虽然维护的是递减栈，但是栈中数字并不是存递减的高度，而是递减的高度的**坐标**。

class Solution {
        
    public:
        int trap(vector<int>& height) {
        
            int n = height.size();
            if(n<=2) return 0;
            int res = 0;
            stack<int> s;
            
            for(int i=0;i<n;++i) {
        
                if(s.empty()||height[i]<=height[s.top()])
                    s.push(i);//递减则入递减栈
                else {
        
                	//出现非递减的元素，则为右边界，将栈当中小于此边界的元素弹出计算可储水的量。
                    while(!s.empty()&&height[i]>height[s.top()]) {
        
                    //这里一定是while循环 如果左边有多个元素小于当前压栈值 持续出栈计算面积 
                        int t = s.top();
                        s.pop();
                        //特殊情况 就是说没有左边界，此时需要判断栈是否为空如果为空直接跳出
                        if(!s.empty()) {
        
                        //根据左右边界计算面积
                            int l = s.top();
                            int h = min(height[l],height[i]) - height[t];
                            int w = i - l - 1;
                            res += h*w;
                        }
                    }
                    s.push(i);
                }
            }
            return res;
        }
    };

每一个元素只有一次入栈和出栈，所以整体的时间复杂度为o(n)。

[LeetCode Monotone Stack Summary]: http://www.cnblogs.com/grandyang/p/8887985.html
[70]: /images/20220506/c709017675544ce99301c05f49cfc495.png