Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Example

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Note

有两种方法。一种是利用Stack去找同一层的两个边，不断累加寄存。如[2, 1, 0, 1, 2]，2入栈，1入栈，0入栈，下一个1大于栈顶元素0，则计算此处的雨水量加入res，此过程中0从栈中弹出，1入栈，到下一个2，先弹出1，由于之前还有一个1在栈中，所以计算时高度的因数相减为0，雨水量为0，res无变化，继续pop出栈中的元素，也就是之前的1，此时stack中仍有元素2，说明左边还有边，继续计算底层高度为1，两个值为2的边之间的水量，加入res。
双指针法的思想：先找到左右两边的第一个峰值作为参照位，然后分别向后（向前）每一步增加该位与参照位在这一位的差值，加入sum，直到下一个峰值，再更新为新的参照位。这里有一个需要注意的地方，为什么要先计算左右两个峰值中较小的那个呢？因为在两个指针逼近中间组成最后一个积水区间时，要用较短边计算。

Solution

1. Stack

public class Solution {
    public int trapRainWater(int[] A) {
        Stack<Integer> stack = new Stack<Integer>();
        int res = 0;
        for (int i = 0; i < A.length; i++) {
            if (stack.isEmpty() || A[i] < A[stack.peek()]) stack.push(i);
            else {
                while (!stack.isEmpty() && A[i] > A[stack.peek()]) {
                    int pre = stack.pop();
                    if (!stack.isEmpty()) {
                        res += (Math.min(A[i], A[stack.peek()]) - A[pre]) * (i - stack.peek() - 1);
                    }
                }
                stack.push(i);
            }
        }
        return res;
    }
}

2. Two-Pointer

public class Solution {
    public int trap(int[] A) {
        int left = 0, right = A.length-1, res = 0;
        while (left < right && A[left] < A[left+1]) left++;
        while (left < right && A[right] < A[right-1]) right--;
        while (left < right) {
            int leftmost = A[left], rightmost = A[right];
            if (leftmost < rightmost) {
                while (left < right && A[++left] < leftmost) res += leftmost - A[left];
            }
            else {
                while (left < right && A[--right] < rightmost) res += rightmost - A[right];
            }
        }
        return res;
    }
}