LeetCode42(接雨水)[三种解法:理解动态规划,双指针,单调栈]

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。


这是一道困难题,难度确实有点层次.我们先来朴素思想走一波.
要求能接多少雨水,我们可以具化到每个硅谷,每个硅谷能存多少雨水,那么答案就是每个硅谷的雨水所加之和.
对于每一个高度的柱子,我们要求出它的积水量,是等于它左边高度的最大值与右边高度的最大值中这两个值其中的小值减去当前硅谷的高度.
公式为:

怎么理解这句话呢?为什么不是这个硅谷两旁的高度相比较较小值减去当前硅谷的高度,而是其左右两边的最大值呢.

对于这一小块,我们观察到积水处的左右两边好像跟我们拿其左右两边最大值与它身边两个的最小值所取到的积水处的值是一样的.

我们仔细来看看中间那部分.

这一部分如果取两边的值,我们将会漏掉上方那一个单位的正方形值,所以对于积水处的两旁界限我们应该是选取左右两边的最大值.

而为什么又要减去积水处的高度呢?我们再来看下面这一部分

其实不用我解释,现在看这幅图大家都能理解啦,我们肯定是需要减去它的基础高度值,才能求得实际上空的空间.也就是硅谷的面积.

所以基于这种求值的思路,我们开始来正式解题.

暴力法解题

我们谈到是要取一个硅谷点的左右两边最大值来求值.那么每当我们到达一个结点处,遍历它的左右两边找到其左右的最大值就可以完成这一步骤的计算.但由于每一个结点我们都需要遍历一遍数组,所以时间复杂度为O(²)
我相信大家应该都可以基于暴力能自主完成,这里不做代码解释,下面才是算法重点.

动态规划

我们谈到一个节点的左右两边的最大值.我们可不可以在计算之前,统计好每一个结点的左右两边的最大值.
也就是从左往右开始遍历,我们可以求得每个结点右边的最大值.
rightMax[i]=max(rightMax[i+1],height[i])
同理,从右往左遍历,我们可以求得每个结点左边的最大值.
leftMax[i]=max(leftMax[i−1],height[i])
总之就是在遍历计算前,我们打表把所有每个结点的左右两边的最大值存储好,之后我们要求时直接从打表过后的数组里面取就可
代码为

public int dpMethod(int[] height){
        int[] leftdp = new int[height.length];
        int[] rightdp = new int[height.length];
        int leftMax = 0;
        int rifhtMax = 0;
        int res = 0;
        for(int i = 0;i < height.length;i++){
            leftdp[i] = leftMax = Math.max(height[i],leftMax);
        }
        for(int i = height.length-1;i >= 0;i--){
            rightdp[i] = rifhtMax = Math.max(height[i],rifhtMax);
        }
        for(int i = 0;i < height.length;i++){
            res += Math.min(leftdp[i],rightdp[i]) - height[i]; 
        }
        return res;
    }

时间复杂度为O(n)

单调栈

我们发现硅谷处其实也就是发生破坏一个柱子的单调性时,产生了硅谷.我们可以利用这样一个特性完成题目的解题.对于每一个结点的索引,我们存放于栈中,每当这个结点的高度小于栈顶元素的值(也就是需要循环遍历),我们就将其索引值放于栈中.而遇到破坏单调性,也就是一个柱子的高度大于我们的栈顶元素时.我们将栈顶元素弹出,求得此时硅谷处的值.
公式也就是
res += Min(height[peek],height[i])-height[pop]

需要注意的是

我们应该在栈中无元素时,不用再进行求值,因为此时说明是边界情况,对应此时红框中的情况,当我们计算完pop处之后,下一次循环,我们将弹出peek处的元素,此时它的左边没有元素,也就是对应着此时栈中没有元素.我们不需要再进行求值.

还有一点不同的是,我们遍历处的height[j] 与我们的栈顶元素是有一段宽度的,我们计算面积应该带上宽度的乘积,及宽度长度为 i - peek - 1,对应的情况为

代码为

public int stack(int[] height){
        LinkedList<Integer> rain = new LinkedList();
        int res = 0;
        for(int i = 0;i < height.length;i++){
            while(!rain.isEmpty() && height[rain.peek()] < height[i]){
                int pop = rain.pop();//弹出栈顶元素
                if(rain.isEmpty()){
                    break;
                }
                int left = rain.peek();//获取栈顶元素的值,还在栈中没有弹出
                int h = Math.min(height[i],height[left]) - height[pop];
                res += h * (i - left - 1);
            }
            rain.push(i);
        }
        return res;
    }

时间复杂度为O(n).

双指针

最后一种解法就是我们的双指针啦,也是最快的解法.不需要开辟任何空间,只需要常量级别的空间,而且只需要一次遍历即可完成.

注意到下标 i 处能接的雨水量由 leftMax[i] 和 rightMax[i] 中的最小值决定。由于数组 leftMax 是从左往右计算，数组 rightMax 是从右往左计算，因此可以使用双指针和两个变量代替两个数组。
遍历过程中,我们更新左右两端的最大值.
当左边的值小于右边的值时,我们直接拿着左边的最大值减去当前结点的高度即可.欸?为什么这里我们不需要再次比较左右两端的最大值,选取其中的较小值呢?
注意啦,我们先判断左边的元素是否大于右边的元素,如果大于我们挪动的是右指针,也就是说明如果右边的值没有大于过左边的值,将一直挪动的是右指针,间接性的把左右两端的最大值作了比较.
右边的值小于左边的值是也是如此.

代码为所以

public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int leftMax = 0;
        int rightMax = 0;
        int res = 0;
        while(left < right){
            leftMax = Math.max(leftMax,height[left]);
            rightMax = Math.max(rightMax,height[right]);
            if(height[left] < height[right]){
                res += leftMax - height[left];
                left++;
            }else{
                res += rightMax - height[right];
                right--;
            }
        }
        return res;
    }

时间复杂度为O(n),空间复杂度为O(1)