单调栈

42. 接雨水

给定 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

class Solution {
    public int trap(int[] nums) {
        Stack<Integer> stack = new Stack();
        int ans = 0;
        int l = 0;
        while(l < nums.length) {
            while(!stack.empty() && nums[stack.peek()] < nums[l]){
                int top = stack.pop();
                if(stack.empty())
                    break;
                int h = Math.min(nums[l],nums[stack.peek()])-nums[top];
                int w = l - stack.peek()-1;
                ans += (h*w);
            }
            stack.push(l++);
        }
        return ans;
    }
}

双指针


注意上面的最后一段话

class Solution {
    public int trap(int[] nums) {
        int len = nums.length;
        int left = 0;
        int right = len-1;
        int lm = 0;
        int rm = 0;
        int ans = 0;
        // 最后一定指向的是最高的哪个，得到的数字一定是0，所以不需要=
        while(left < right) {
            if(nums[left] < nums[right]) {
                lm = Math.max(lm,nums[left]);
                ans += (lm-nums[left++]);
            } else {
                rm = Math.max(rm,nums[right]);
                ans+=(rm-nums[right--]);
            }
        }
        return ans;
    }
}