lc42. 接雨水（单调递减栈&双指针）

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

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

单调栈

class Solution {
    int[] stk;
    int tt;
    public int trap(int[] height) {
        int n = height.length;
        stk = new int[n+1];
        int res = 0;
        for(int i = 0; i < n; ++i){
            while(tt > 0 && height[stk[tt]] < height[i]){
                int curHeight = height[stk[tt--]];
                if(tt <= 0) break;          //边界最后一个是没法接雨水的
                int l = stk[tt];             //左边柱子
                int r = i;
                int h = Math.min(height[l],height[r]) - curHeight;
                res += h * (r-l-1);
            }
            stk[++tt] = i;
        }
        return res;
    }
}

双指针

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int max_right = 0, max_left = 0;
        int left = 1, right = n-2;
        int res = 0;
        for(int i = 1; i < n-1; ++i){
            //从左往右更新
            if(height[left-1] < height[right+1]){
                max_left = Math.max(max_left,height[left-1]);
                int min = max_left;
                if(min > height[left])
                    res += min - height[left];
                left++;
            }
            //从右往左更新
            else{
                max_right = Math.max(max_right,height[right+1]);
                int min = max_right;
                if(min > height[right])
                    res += min - height[right];
                right--;
            }
        }
        return res;
    }
}