42 Trapping rain water

https://leetcode.com/problems/trapping-rain-water/

跟11的思路很像，初见杀很难想到吧。

基本上，left和right所在位置能trap的水量取决于其左边和右边最大值中较小的那个，虽然每次left和right的水量都能确定，但是我们事实上只会确定一个，毕竟所有的位置都能遍历到，所以需要移动哪个就确定哪个

class Solution {
    public int trap(int[] height) {
        int leftMax = 0;
        int rightMax = 0;
        int i = 0;
        int j = height.length-1;
        int sum = 0;
        while (i <= j) {
           leftMax = Math.max(leftMax, height[i]);
            rightMax = Math.max(rightMax, height[j]);
            if (leftMax < rightMax) {
            // i左边的bar已经探索完了，leftMax确定是它的短板了，所以它能装的水就固定了
                sum += leftMax - height[i++];
            } else {
                sum += rightMax - height[j--];
            }
        }
        return sum;
    }
}

更容易想到的思路是mono stack，但是要记得mono stack只能找到第一个大的值，但是能装多少取决于最大值，所以思路是固定水的底，然后一层一层往上加，举个例子就

方法1是这样的

用mono stack是这样的

class Solution {
    public int trap(int[] height) {
        // decreasing stack
        Deque<Integer> stack = new ArrayDeque<>();
        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int idx = stack.pop();
                if (stack.isEmpty()) {
                    continue;
                }
                int left = stack.peek();
                int right = i;
                sum += (right - left - 1) * (Math.min(height[left], height[right])-height[idx]);
            }
            stack.push(i);
        }
        return sum;
    }
}