7.接雨水【好难QAQ】

42. 接雨水

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

示例 1：

输入：height = [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 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

方法1：按行计算

思路：空心count++；实心sum+=count; 逐层计算

i 逐个遍历每一个块。按层所以判断空是：height[i] 与层数相比

太难了啊QAQ 还超时交不上去。

class Solution {
    public int trap(int[] height) {
        int iters = 0, n = height.length, sum = 0;
        int count=0;
        boolean flag=false;
        //求最大值
        for (int num : height) {
            iters = Math.max(iters, num);
        }

        for (int iter = 1; iter <= iters; iter++) {
            flag = false;
            count=0;
            for (int i = 0; i < n; i++) {
                if(flag && height[i]<iter){   //空
                    count++;
                }
                if(height[i]>=iter){      //实心的
                    sum +=count;
                    count=0;
                    flag=true;
                }
            }
        }
        return sum;
    }
}

 

方法2：动态规划

dp表：max_left[] ; max_right[] 。max_left[ i ]表示当前位置左边最高的墙【不包含当前位置，因为需要 墙-height[ i ] ，计算雨水深度】；max_right[ i ] 同理。

dp[i] = max(dp[i-1],height[i-1])

竖着遍历一遍数组，比较max_left[ i ] ， max_right[ i ] 中小的那个。小的在于正在求的列比较

OS:妙啊~还得是dp

class Solution {
    public int trap(int[] height) {
            // dp 按列
            int sum = 0;
            int[] max_left = new int[height.length];
            int[] max_right = new int[height.length];


            // 比较当前位置之前 最高的 并记录下来【从左往右】
            
            for(int i = 1; i<height.length-1;i++){
                // max_left[i]=Math.max(max_left[i-1],height[i]);
                // 当前列接水量 = min(左边最高墙, 右边最高墙) - 当前列高度,所以不能和height[i]比较
                max_left[i] = Math.max(max_left[i-1],height[i-1]);
            }
            for(int i = height.length-2;i>=0;i--){
                max_right[i] = Math.max(max_right[i+1],height[i+1]);
            }

            int min = 0;
            for(int i = 1;i<height.length-1;i++){
                min = Math.min(max_left[i],max_right[i]);  //左右两边较矮的那个墙
                if(height[i]<min){
                    sum+=min-height[i];

                }
            }
        return sum;
}}

 

方法3：双指针

改造版dp

max_left [ i ] 和 max_right [ i ] 数组中的元素我们其实只用一次，然后就再也不会用到了。

可以不用数组，只用一个元素就行了。变形为——> max_left + max_right [ i ]

class Solution {
    public int trap(int[] height) {
            // dp 按列
            int sum = 0;
            int max_left = 0;
            int[] max_right = new int[height.length];
      
            for(int i = height.length-2;i>=0;i--){
                max_right[i] = Math.max(max_right[i+1],height[i+1]);
            }

            int min = 0;
            for(int i = 1;i<height.length-1;i++){
                max_left = Math.max(max_left,height[i-1]);   //当前位置左边最高的墙
                min = Math.min(max_left, max_right[i]);  //左右两边较矮的那个墙
                if(height[i]<min){
                    sum+=min-height[i];
                }
            }
        return sum;
}}