算法——接雨水

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

解题思路：利用单调栈的思想。

1. 从左向右遍历，栈中不断存储左侧的柱子，而且是单调下降的。
2. 当后者的柱子长度大于前者的，就会形成一个蓄水区域，当一个蓄水区域形成之后，短的柱子就没有用了，就将其踢出。
3. 利用一个base变量，去掉底部的已经被计算过的蓄水区域部分。
4. 因为上一步计算的都是右边高于左边的面积，所以需要加上右边高于base且低于左边的部分。
5. 最后将当前柱子压入栈中。

class Solution {
    public int trap(int[] height) {
        Deque<Integer> stack = new LinkedList<>();
        int res = 0, base = 0;
        for(int i = 0; i < height.length; i++) {
            while(!stack.isEmpty() && height[stack.peek()] <= height[i]) {
                int t = stack.pop();
                res += (height[t] - base) * (i - t - 1);
                base = height[t];
            }

            if(!stack.isEmpty()) res += (height[i] - base) * (i - stack.peek() - 1);
            stack.push(i);
        }

        return res;
    }
}