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;
    }
}

代码执行结果：