leetcode42.接雨水

题目链接

题解: stack

本题的类似题目：leetcode84题：柱状图中的最大图形。本题 题解 附上~

接雨水这道题有多种思路：暴力,dp,双指针等，目前的做题的tag为栈，队列，所以题解只使用栈来解决，后续会补充dp，以及dp优化的思路。
对于输入的数组为:[0,1,0,2,1,0,1,3,2,1,2,1],盛接雨水的情况为：

首先，我们要思考，什么情况下，能盛接雨水？
如果柱子的高度变化如下所示：

就可以达到盛接雨水的作用。

我们使用栈来保存柱子。从头到尾遍历：栈为空，就压入一个柱子；栈不为空的时候，如果当前遍历到的柱子的高度小于栈顶的柱子高度，说明趋势在不断向下，会积水，但是没有闭合；如果当前遍历的柱子大于栈顶保存的柱子的高度了，那说明趋势已经向上了，构成了存储雨水的条件，我们就计算出积水的量，然后将当前的柱子继续入栈，作为新的边界。
综上所述：

1. 当前的柱子的高度小于栈顶柱子高度，入栈，指针后移
2. 当前柱子的高度大于栈顶柱子高度，出栈，计算雨水体积直至当前柱子的高度不大于栈顶的高度，或者栈为空。

对于步骤二，计算的思路如下：
例如：对于数组[3,2,1,0,3]而言
首先将3,2,1,0的下标依次入栈，遍历到最后一个元素3的时候，构成了先抑后扬的趋势，可以计算出积水的面积了，计算思路如下：
第一步，需要算出如下蓝色部分的面积

第二步，算出第二层积水的面积：

最后算出第三层积水的面积：

最后既满足了当前柱子的高度不大于栈顶的高度，也满足了栈为空的条件。
按层计算雨水体积的代码还是比较难写的，我也是看了别人的代码，希望大家多加练习，好好举例体会。

代码如下：

class Solution {
    public int trap(int[] height) {
        if(height == null || height.length== 0){
            return 0;
        }
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        for(int i = 0;i < height.length;i++){
            while(!stack.isEmpty() && height[i] > height[stack.peek()]){
                int h = height[stack.peek()];
                stack.pop();
                if(stack.isEmpty()){
                    break;
                }
                int distance = i - stack.peek() - 1;
                int min = Math.min(height[i],height[stack.peek()]);
                res += (min - h) * distance;
            }
            stack.push(i);
        }
        return res;
    }
}

代码执行结果：