MENU

LeetCode42. 接雨水

August 13, 2018 • Read: 589 • LeetCode

题目链接: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;
    }
}
最后编辑于: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code