leetcode42.接雨水

作者: 憨憨二师兄 | 来源:发表于2020-04-27 13:01 被阅读0次

    题目链接

    题解: stack

    本题的类似题目:leetcode84题:柱状图中的最大图形。本题 题解 附上~

    接雨水这道题有多种思路:暴力,dp,双指针等,目前的做题的tag为栈,队列,所以题解只使用栈来解决,后续会补充dp,以及dp优化的思路。
    对于输入的数组为:[0,1,0,2,1,0,1,3,2,1,2,1],盛接雨水的情况为:


    首先,我们要思考,什么情况下,能盛接雨水?
    如果柱子的高度变化如下所示:

    就可以达到盛接雨水的作用。

    我们使用栈来保存柱子。从头到尾遍历:栈为空,就压入一个柱子;栈不为空的时候,如果当前遍历到的柱子的高度小于栈顶的柱子高度,说明趋势在不断向下,会积水,但是没有闭合;如果当前遍历的柱子大于栈顶保存的柱子的高度了,那说明趋势已经向上了,构成了存储雨水的条件,我们就计算出积水的量,然后将当前的柱子继续入栈,作为新的边界。
    综上所述:
    1. 当前的柱子的高度小于栈顶柱子高度,入栈,指针后移
    2. 当前柱子的高度大于栈顶柱子高度,出栈,计算雨水体积直至当前柱子的高度不大于栈顶的高度,或者栈为空。

    对于步骤二,计算的思路如下:
    例如:对于数组[3,2,1,0,3]而言
    首先将3,2,1,0的下标依次入栈,遍历到最后一个元素3的时候,构成了先抑后扬的趋势,可以计算出积水的面积了,计算思路如下:
    第一步,需要算出如下蓝色部分的面积


    第二步,算出第二层积水的面积:

    最后算出第三层积水的面积:

    最后既满足了当前柱子的高度不大于栈顶的高度,也满足了栈为空的条件。
    按层计算雨水体积的代码还是比较难写的,我也是看了别人的代码,希望大家多加练习,好好举例体会。

    代码如下:

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

    代码执行结果:


    相关文章

      网友评论

        本文标题:leetcode42.接雨水

        本文链接:https://www.haomeiwen.com/subject/dwdywhtx.html