LeetCode日记–42.Trapping Rain water

发布于 2020-09-25  144 次阅读


碎碎念:今天上了方老师和腾讯一起开的微信小程序开发,感觉开发也挺好玩的,而且自己对开发的了解几乎为零。今年奖学金又只是普通单项,唉,努力刷题找工吧!现在这样按照tag乱刷感觉不是很有效率,我决定明儿开始跟着剑指offer刷,把常见的套路先见见面先。

题目如下:

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.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

我的思路:

这题是我最近做得最久的一道题了(不愧是hard)。刚刚拿到这道题的时候,我还觉得很简单。我的思路是使用快慢针,从左向右遍历,当慢指针是右边暂时最高的,快指针遍历到比慢指针高的地方就开始算每个格子存的水量(height[leftPointer]-height[i]),但是后来发现还有可能出现后面有更低的边界,也就是说每次更新的慢指针都是最高的,很快他就不能作为木桶的短板去界定其他的水槽了。

那我只想到还能够暴力遍历。也就是每个格子都向左右遍历,得到min(大于本格的柱子),用大于本格的最小高度来得到本格的存水量。

但是这样的话需要n^2次遍历。

代码如下:

public int trap(int[] height) {
    int ans = 0;
    int size = height.length;
    for (int i = 1; i < size - 1; i++) {
        int max_left = 0, max_right = 0;
        for (int j = i; j >= 0; j--) { //Search the left part for max bar size
            max_left = Math.max(max_left, height[j]);
        }
        for (int j = i; j < size; j++) { //Search the right part for max bar size
            max_right = Math.max(max_right, height[j]);
        }
        ans += Math.min(max_left, max_right) - height[i];
    }
    return ans;
}

作者:LeetCode
链接:https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

官方思路:

方法二:

可是上面的暴力方法每一次都需要遍历,那么我们有没有什么办法可以把一次遍历的结果存下来呢?这时候就有一个很厉害的动态编程的思想。

我们分别从左往右和从右往左遍历了这个水槽,把leftMax界定的部分和rightMax界定的部分用数组存下来。这时候每个格子取两次界定值中的最小值。

官方代码如下(我没自己实现):

public int trap(int[] height) {
    if (height == null || height.length == 0)
        return 0;
    int ans = 0;
    int size = height.length;
    int[] left_max = new int[size];
    int[] right_max = new int[size];
    left_max[0] = height[0];
    for (int i = 1; i < size; i++) {
        left_max[i] = Math.max(height[i], left_max[i - 1]);
    }
    right_max[size - 1] = height[size - 1];
    for (int i = size - 2; i >= 0; i--) {
        right_max[i] = Math.max(height[i], right_max[i + 1]);
    }
    for (int i = 1; i < size - 1; i++) {
        ans += Math.min(left_max[i], right_max[i]) - height[i];
    }
    return ans;
}

作者:LeetCode
链接:https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

终于,我们把时间复杂度从O(n^2)降到了O(n),不过空间复杂度上升到了O(n).

不过刚刚的方法依然需要遍历两遍,那么我们有什么办法可以只遍历一遍呢?

方法三:

这时我们想象有两块板子分别从左右两边向中间靠拢,如果两板向内移动时,中间有更高的地方,则碰到更高的地方之前都是由当前的min(leftMax,rightMax)来界定的,如果中间都比目前的低则说明整个水槽都由min(leftMax,rightMax)界定。也就是说我们只需要每次移动左右指针中的较小的那个(直到找到更高的就可以了)就可以了。

如果看到我这里依然觉得不明白(没有图示不明白很正常啊!),就看看官方题解中的演示动画,非常优美,清晰。

我实现的代码如下:

class Solution {
    public int trap(int[] height) {
        int leftPointer=0,rightPointer = height.length-1;
        int leftMax=0,rightMax=0;
        int res =0;
        while(leftPointer<rightPointer){
            if(height[leftPointer]<=height[rightPointer]){
                if(height[leftPointer]>=leftMax)
                    leftMax=height[leftPointer];
                else
                    res+=leftMax-height[leftPointer];
                ++leftPointer;
            }
            else{
                if(height[rightPointer]>=rightMax)
                    rightMax=height[rightPointer];
                else
                    res+=rightMax-height[rightPointer];
                --rightPointer;
            }
        }
        return res;
    }
}

唉,hard果然对于我这种彩笔还是太难了,距离找实习还有不到半年了,要加把劲了啊!


你好哇!欢迎来到雷公马碎碎念的地方:)