L42

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

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

示例:

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

1.一行一行的计算

class Solution {
    public int trap(int[] height) {
        int sum  = 0;
        int max = getMax(height);
        for(int i = 1; i <= max; i++){
            //一行一行的处理
            int tmp = 0;
            boolean flag = false;
            for(int j = 0; j < height.length; j++){
                if(flag && height[j] <i){//只有小于i的时候才有空位置接水
                    tmp++;
                }
                if(height[j] >= i){//满足情况时，说明水可以被封起来，才可以结算
                    sum += tmp;
                    tmp = 0;
                    flag = true;//即只有开头有>= i的时候，才能更新tmp
                }
            }
        }
        return sum;
    }
    int getMax(int[] height){
        int max = 0;
        for(int i = 0; i < height.length; i++){
            max = Math.max(max, height[i]);
        }
        return max;
    }
}

2.动态规划，一步步精简

2.1一列一列，分别比较两边的最大值

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int ans = 0;
        for(int i = 1; i < len - 1; i++){//必然不会在两端
            int left = 0, right = 0;
            for(int j = 0; j < i; j++){//找最大值,要考虑两端
                left = Math.max(left, height[j]);
            }
            for(int j = i + 1; j < len; j++){
                right = Math.max(right, height[j]);
            }
            int min = Math.min(left, right);
            if(height[i] < min){
                ans  += (min - height[i]);
            }
        }
        return ans;
    }
}

2.2利用数组存储起来
但是空间复杂度过大

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int ans = 0;
        int left[] = new int[len];
        int right[] = new int[len];
        for(int i = 1; i < len; i++){//从1开始
            left[i] = Math.max(height[i - 1], left[i - 1]);
        }
        for(int i = len - 2; i >= 0; i--){//len - 2开始，不然会越界
            right[i] = Math.max(height[i+ 1], right[i + 1]);
        }
        for(int i = 1; i < len - 1; i++){//必然不会在两端
            
            int min = Math.min(left[i], right[i]);
            if(height[i] < min){
                ans  += (min - height[i]);
            }
        }
        return ans;
    }
}

2.3缩小空间复杂度
尝试压缩数组，因为每一个元素就用了一次，看是否能够用单一变量来替代
先将left数组进行压缩，但是right是无法压缩的

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int ans = 0;
        
        int right[] = new int[len];
        
        for(int i = len - 2; i >= 0; i--){//len - 2开始，不然会越界
            right[i] = Math.max(height[i+ 1], right[i + 1]);
        }
        int left = 0;
        for(int i = 1; i < len - 1; i++){//必然不会在两端
            left = Math.max(left, height[i - 1]);//减少空间复杂度
            int min = Math.min(left, right[i]);
            if(height[i] < min){
                ans  += (min - height[i]);
            }
        }
        return ans;
    }
}

运用双指针的方法

class Solution {
    public int trap(int[] height) {
        int len = height.length;
        int ans = 0;
        int left = 1;//指针,表示当前需要计算的位置
        int right = len -2;
        int max_left = 0, max_right = 0;//记录两端最值
        for(int i = 1; i < len - 1; i++){//必然不会在两端,这里表示计算的次数

            if(height[left - 1] < height[right + 1]){//从左向右
                max_left = Math.max(max_left, height[left - 1]);
                if(height[left] < max_left){
                    ans += max_left -  height[left];
                }
                left++;//继续移动
            }else{
                max_right = Math.max(max_right, height[right + 1]);
                if(height[right] < max_right){
                    ans += max_right - height[right];
                }
                right--;
            }
        }
        return ans;
    }
}

转载自原文链接, 如需删除请联系管理员。

原文链接：L42，转载请注明来源！