单调队列

42. 接雨水

image.png

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

早上看到推送这道题就做一下，看了图就知道是个单调队列，以前都会。然而在草稿本上推了有个把小时还没开动写代码（现在太弱了！！！）

写个几十行代码+调试又一个多小时。。。言归正传开始分析

情况可分为两种2 0 1（1 0 1型归在这类之中） 或 1 0 2型

image.png

首先，2 0 1 型以高度为1为基准从后往前遍历，碰到较他更高或者相等的高度为止，比1低的高度0只能上升到1的高度。1 0 2型从图上也能直接看出，能储存雨水的数量为1。区别在于2 0 1 型现在变成了 2 1 1，若后面的柱子比1高就能储水，即对结果有作用。1 0 2 型变成1 1 2后，无论后面柱子高低，起作用的只可能是2的高度。这里就引入单调队列的思想，保证前面的数呈单调递减。若新的数字小于末尾的数字，则直接加入队尾，否则往前遍历，直到像2 0 1型碰到比他大（或者相等）的数为止,将低于他的数字增加到与他相同为止，累计得到结果。

使用6 4 3 2 5找一下加水的感觉，

1. 高度5往前遍历到高度2，继续往前遇到3，将2加到较小值3的高度，即算式 （位置5 - 位置3 - 1）*（水位3 - 水位2），累计为1

2. 继续往前遇到4，将高度为3的增加到4（包括原本就是3的和刚加到3的2），即算式 （位置5 - 位置2 - 1）*（水位4 - 水位3），累计为1+2

3. 当高度5遇到高度6，撞了墙，变成了与2 0 1型一样，因为现在水位为4，只能加到5的高度，即算式（位置5 - 位置1 -1）* （水位5 - 水位4）

image.png

class Solution {

    public int trap(int[] height) {
        // 这里用了栈的后进先出
        Stack<Integer> stack = new Stack<>();
        int ans = 0;
        for (int i = 0; i < height.length; i++) {
            int pre = -1;

            while (!stack.isEmpty()) {
                int right = stack.pop();
                if (height[i] >= height[right]) {
                    if (pre != -1) {
                        ans += (i - right - 1) * (height[right] - height[pre]);
                    }
                    pre = right;
                    continue;
                } else {
                    if (pre != -1) {
                        ans += (i - right - 1) * (height[i] - height[pre]);
                    }
                    //比栈尾小，加回去
                    stack.push(right);
                    break;
                }
            }

            stack.push(i);
        }
        return ans;
    }
}

题目还有多种解法，暴力递归都行，上面代码也就自己按照逻辑敲了一下可能也没那么标准，欢迎学习讨论。