[刷题]Leetcode.42 接雨水

传送门
题目描述:
1581158692(1).png

一道困难题,看题解的时候说面试经常问,就记录一下这一题。
图中黑色的代表柱子,蓝色的代表水,最终求解蓝色的面积。

这道题从整体去考虑,没有思路。
看了题解(传送门)说要单个单个考虑,是从列来看的。

对于单个列来说
这个列能存的雨水 = MIN( 这个列左边的最高高度,这个列右边的最低高度 ) - 这个列的高度
当然 最低只能为0
找到这个规律 是解这道题的关键, 可以结合图理解这个规律

那么解法也很容易想到了
对每一位置,我们找到这个位置左边的最高高度和这个位置右边的最高高度,然后按规律计算即可。
我们可以用一个数组保存每个位置左边的最高高度,从左往右遍历;求右边最高高度,从右往左同理;
代码如下:

public int trap(int[] height) {
        if(height.length<2) return 0;
        int[] l_max = new int[height.length];
        int[] r_max = new int[height.length];
        l_max[0] = height[0];
        r_max[height.length-1]  = height[height.length-1];
        for(int i=1;i<height.length;i++){
            l_max[i] = Math.max(l_max[i-1], height[i]);
        }
        for(int i=height.length-2;i>=0;i--){
            r_max[i] = Math.max(r_max[i+1],height[i]);
        }

        int ans = 0;
        for (int i=0;i<height.length;i++){
            ans += Math.max ((Math.min(l_max[i],r_max[i])-height[i]),0);
        }
        return ans;

    }

只有三次从头到尾的遍历,因此时间复杂度O(N);用了两个辅助数组,空间复杂度O(N)。

但空间复杂度可以进一步压缩为O(1)
我们用两个指针left,right分别指向左边的柱子和右边的柱子,并记录此时[0,...,left]的最高高度,我们记为l_max, [right,...,N]的最高高度,我们记为r_max。
在遍历的某个时刻,我们比较l_max,r_max,假如l_max<r_max 那么我们可以知道left左侧的最高高度为l_max,右侧的最高高度我们不能确定,但结合上面所说的规律,这足以计算left位置处的雨水面积了,因为我们取左侧最高和右侧最高中的小的那个,而此时l_max<r_max,我们使用l_max就足够了。
而当r_max<=l_max 时同理;
这样,我们不需要用辅助数组,只需要两个变量即可,代码如下:

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

评论

暂无评论