LeetCode42. 接雨水

题目链接：LeetCode42

有人说用贪心，我觉得这是一个单调栈的板子题，构建一个单调递减栈（栈底到栈顶是递减的），要想能够收集雨水，栈中至少要两个数字，才能形成一个坑，先pop一个数字，这个数字就是最低值，再peek一个数字，peek的数字和遍历的到的值进行比较，较小的值减去最低值的高度，得出的这个高度就是能蓄水的高度，底就是做右边界的值相减

class Solution {
    public int trap(int[] height) {
        if(height == null || height.length == 0) 
            return 0;
        int sumArea = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for(int right = 0;right < height.length;right++) {
            while(!stack.isEmpty() && height[stack.peek()] < height[right]) { 
                if(stack.size() >= 2) {
                    int j = stack.pop();
                    int left = stack.peek();
                    int curArea = (Math.min(height[right],height[left]) - height[j]) * (right - left - 1);
                    sumArea += curArea;
                }
                else
                    stack.pop();
            }
            stack.push(right);
        }
        return sumArea;
    }
}