原题

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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例：

输入： [0,1,0,2,1,0,1,3,2,1,2,1] 输出： 6

解法

思想

每一列能存下的雨水单位等于左右最高两列当中的较矮一列与当前高度的高度差。

如图，第五列的积雨水量，等于左边最高一列（第四列left）和右边最高一列（第八列right）的较矮一列（left）与当前列高度的高度差（2-1=1）

如果两边有一边没有比当前列高的列，则当前列不会积水。

代码

我一开始是这样写的：

class Solution {
    public int trap(int[] height) {
        int total = 0;
        int count = height.length;
        Integer[] left = new Integer[count];
        Integer[] right = new Integer[count];
        for(int i = 0;i<count;i++){
            for(int j = 1;j<=i;j++){//更新左边所有列的right
                if(right[j]==null||height[i]>right[j]) right[j] = height[i];
            }
            for(int j = i;j<count-1;j++){//更新右边所有列的left
                if(left[j]==null||height[i]>left[j]) left[j] = height[i];
            }
        }
        for(int i = 0;i<count;i++){
            if(left[i]==null || right[i] == null) continue;
            total += (Math.min(left[i],right[i])-height[i]);
        }
        return total;
    }
}

时间复杂度达到了N²级别，那么如何优化呢？

不必使用null来表示没有比当前列高的列，即使两列相等，高度差也是0，相当于不积水。
利用动态规划的思想，如果前一列的left比当前列高，则当前列的left也等于前一列的left。对于right也是一样的。

优化后：

class Solution {
    public int trap(int[] height) {
        int total = 0;
        int count = height.length;
        if(count==0) return 0;
        Integer[] left = new Integer[count];
        Integer[] right = new Integer[count];
        left[0] = height[0];
        right[count-1] = height[count-1];
        for(int i = 1;i<count;i++){//从左向右更新left
            if(height[i]>left[i-1]) left[i] = height[i];
            else left[i] = left[i-1];
        }
        for(int i = count-2;i>=0;i--){//从右向左更新right
            if(height[i]>right[i+1]) right[i] = height[i];
            else right[i] = right[i+1];
        }
        for(int i = 0;i<count;i++){
            total += (Math.min(left[i],right[i])-height[i]);
        }
        return total;
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode42-%e6%8e%a5%e9%9b%a8%e6%b0%b4/

leetcode42-接雨水

原题

解法

思想

代码

相关推荐

发表回复