【动态规划专题】LeetCode 42. 接雨水-跟着帅地玩副业，开拓第二曲线PlayOffer

宁永久会员 2023年3月14日下午4:49

两种方法，双指针节省空间复杂度

class Solution {
    public int trap(int[] height) {
        //左边最大的，右边最大的，他们当中小的值可以加上
        //但是怎么找到两边最大的呢？

        int len = height.length;
        // int[] l_max = new int[len];
        // int[] r_max = new int[len];
        //1提前准备好
        // l_max[0] = height[0];
        // for(int i = 1; i < len; i++){
        //     l_max[i] = Math.max(l_max[i - 1], height[i]);
        // }
        // r_max[len - 1] = height[len - 1];
        // for(int i = len - 2; i >= 0; i--){
        //     r_max[i] = Math.max(r_max[i + 1], height[i]);
        // }
        // int sum = 0;
        // for(int i = 1; i < len - 1; i++){
        //     sum += Math.min(l_max[i], r_max[i]) - height[i];
        // }
        // return sum;
        //2双指针
        int left = 0;
        int right = len - 1;
        int l_max = 0;
        int r_max = 0;
        int sum = 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){
                sum += l_max - height[left];
                left++;
            }else{
                sum += r_max - height[right];
                right--;
            }
        }
        return sum;
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月20日下午6:59

def trap(height: list[int]) -> int:
    if len(height) == 0:
        return 0
    res = 0
    left = 0
    right = len(height) - 1

    # l_max存放【0。left】上的最大值
    l_max = height[0]
    # r_max存放[right，-1]上的最大值
    r_max = height[-1]

    while left <= right:
        l_max = max(l_max,height[left])
        r_max = max(r_max,height[right])

        if l_max < r_max:
            res += (l_max - height[left])
            left += 1
        else:
            res += (r_max - height[right])
            right -= 1
    return res

0 赞同 0 条回复

lucca 普通 2023年1月19日下午10:42

双指针，巧妙避开DP

时间复杂度 O(N)
空间复杂度 O(1)
找到最大值，从左到最大值遍历一次，再从右到最大值遍历一次即可
有多个最大值也没关系，任取一个即可，不影响结果

class Solution {
    public int trap(int[] height) {
        int sum = 0;
        int maxId = 0;
        for (int i = 1; i < height.length; i++)
            if (height[i] > height[maxId]) maxId = i;

        int lmax = 0;
        for (int i = 0; i < maxId; i++) {
            if (lmax <= height[i]) lmax = height[i];
            else sum += (lmax - height[i]);
        }
        int rmax = 0;
        for (int i = height.length - 1; i > maxId; i--) {
            if (rmax <= height[i]) rmax = height[i];
            else sum += (rmax - height[i]);
        }
        return sum;
    }
}

0 赞同 0 条回复

@ 普通 2022年12月28日下午12:12

class Solution {

    //动态规划
    //时间复杂的：O(N)  空间复杂度：O(N)
    public int trap(int[] height) {
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];
        int lMax = 0;
        int rMax = 0;
        int res = 0;

        //找出height每个元素的左边的最大值
        for (int i = 0; i < height.length; i++) {
            if(height[i] >= lMax)
                lMax = height[i];

            leftMax[i] = lMax;
        }

        //找出height每个元素的右边的最大值
        for (int i = height.length - 1; i >= 0; i--) {
            if(height[i] >= rMax)
                rMax = height[i];

            rightMax[i] = rMax;
        }

        //每个位置可存储的雨水数为：左右两边最大值取其最小的那个 - 当前位置的柱子高度
        for (int i = 0; i < height.length; i++) {
            res += Math.min(rightMax[i], leftMax[i]) - height[i];
        }


        return res;
    }

    //双指针
    //时间复杂的：O(N)  空间复杂度：O(1)
    public int trap2(int[] height) {
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (leftMax < rightMax) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }
        return ans;
    }


}

0 赞同 0 条回复

y 普通 2022年12月3日下午5:57

var trap = function(height) {
   let n = height.length;
   let res = 0;
   let l_max = new Array(n).fill(0);
   let r_max = new Array(n).fill(0);

   l_max[0] = height[0];
   r_max[n - 1] = height[n - 1];

   for (let i = 1; i < n; i++) {
       l_max[i] = Math.max(l_max[i - 1], height[i]);
   }

   for (let j = n -2; j >= 0; j--) {
       r_max[j] = Math.max(height[j], r_max[j + 1]);
   }

   for (let i = 0; i< n; i++) {
     res+= Math.min(l_max[i], r_max[i]) - height[i]
   }
  return res;
};

时间O(n)
空间O(n)

0 赞同 0 条回复

Tolkien 永久会员 2022年12月1日下午3:43

/**
     * 方法一：暴力
     * 时间复杂度：O(n^2), 空间复杂度：O(1)
     * 对于每一个柱子，它能接的雨水量rainfall[i]为min(leftMax, rightMax)-height[i]
     * 其中leftMax为该柱子左最高的柱子的高度，rightMax同理
     */
    public static int trap(int[] height) {
        int rainfall = 0;
        int n = height.length;

        // 遍历每根柱子
        for (int i = 0; i < n; i++) {
            int leftMax = 0, rightMax = 0;
            // 遍历该柱子的左边柱子和右边柱子
            for (int j = 0; j < i; j++) {
                leftMax = Math.max(leftMax, height[j]);
            }
            for (int k = i; k < n; k++) {
                rightMax = Math.max(rightMax, height[k]);
            }
            int rainfallInOneColumn = Math.min(leftMax, rightMax)-height[i];
            if (rainfallInOneColumn > 0) {
                rainfall += rainfallInOneColumn;
            }
        }

        return rainfall;
    }

    /**
     * 方法二：备忘录优化
     * 时间复杂度：O(n), 空间复杂度：O(n)
     * 暴力方法中重复计算i左边和右边最高柱子的柱子，此方法通过备忘录提前记录，减少重复计算
     */
    public static int trap2(int[] height) {
        int rainfall = 0;
        int n = height.length;

        // 备忘录
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        // 初始化备忘录
        leftMax[0] = height[0];
        rightMax[n-1] = height[n-1];

        // 从左向右遍历，记录height中的最大值
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i-1], height[i]);
        }
        // 从右向左遍历，记录height中的最大值
        for (int i = n-2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i+1], height[i]);
        }

        for (int i = 0; i < n; i++) {
            int min = Math.min(leftMax[i], rightMax[i]);
            rainfall += min-height[i];
        }

        return rainfall;
    }

    /**
     * 双指针
     * 时间复杂度：O(n)，空间复杂度：O(1)
     * 在备忘录的基础上，优化备忘录的空间
     * 从height的左右两边开始，向中间遍历，分别获得左边和右边局部的最大高度
     * 若左边的最大高度 < 右边的最大高度，则计算左边局部的柱子的承水量
     */
    public static int trap3(int[] height) {
        int n = height.length;
        int leftMax = height[0], rightMax = height[n-1];
        int left = 0, right = n-1;
        int result = 0;

        // 向中间遍历，分别获得左边和右边局部的最大高度
        while (left <= right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);

            if (leftMax < rightMax) {
                result += leftMax - height[left];
                left++;
            }
            else {
                result += rightMax - height[right];
                right--;
            }
        }

        return result;
    }

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月28日上午12:59

双指针法时间复杂度为O（n），空间复杂度为O（1）

public class Trap {
    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        int trap = trap3(height);
        System.out.println(trap);
    }
    public static int trap1(int[] height) {
        int n = height.length;
        int res = 0;
        for(int i = 1;i < n-1;i++){
            int l_max = 0;
            int r_max = 0;
            for(int j = i;j < n;j++){
                r_max = Math.max(r_max,height[j]);
            }
            for(int j = i;j >= 0;j--){
                l_max = Math.max(l_max,height[j]);
            }
            int x = Math.min(r_max,l_max) - height[i];
            res = res + x;
        }
        return res;
    }
    public static int trap2(int[] height) {
        int n = height.length;
        int res = 0;
        int[] l_max = new int[n];
        int[] r_max = new int[n];
        l_max[0] = height[0];
        r_max[n-1] = height[n-1];
        //l_max[i]表示位置 i 左边最高的柱子高度，r_max[i]表示位置 i 右边最高的柱子高度。
        for(int j = 1;j < n;j++){
            l_max[j] = Math.max(l_max[j-1],height[j]);

        }
        for(int j = n-2;j >= 0;j--){
            r_max[j] = Math.max(r_max[j+1],height[j]);
        }
        for(int i = 1;i < n-1;i++){
            res += Math.min(r_max[i],l_max[i]) - height[i];
        }
        return res;
    }
    //双指针法
    public static int trap3(int[] height) {
        int n = height.length;
        int res = 0;
        int left = 0;
        int right = n - 1;
        int l_max = height[0];
        int r_max = height[n-1];
        while(left <=right){
            l_max = Math.max(l_max,height[left]);
            r_max = Math.max(r_max,height[right]);
            if(l_max < r_max){
                res += l_max - height[left];
                left++;
            }else{
                res += r_max - height[right];
                right--;
            }
        }
        return res;
    }
}

0 赞同 0 条回复

Mooby 普通 2022年11月27日下午4:39

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

时间：O(n)，空间：O(n)

0 赞同 0 条回复

just 普通 2022年11月27日上午11:45

//使用动态规划，不过这题目最好的还是单调栈
class Solution {
public:
int trap(vector& height) {
int res=0;
vector l(height.size(),0);
vector r(height.size(),0);
l[0]=height[0];
r[height.size()-1]=height[height.size()-1];
for(int i=1;i<height.size();++i){
l[i]=max(height[i],l[i-1]);
}
for(int i=height.size()-2;i>=0;–i){
r[i]=max(height[i],r[i+1]);
}
for(int i=1;i<height.size()-1;++i){

        res+=(min(l[i],r[i])-height[i]);
    }
    return res;

}

};

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月25日下午11:31

双指针。时间复杂度O(n^2)空间复杂度O(n)

//双指针
class Solution {
    public int trap(int[] height) {
        int sum = 0;
        //排除首尾
        for(int i = 1;i < height.length - 1;i++){
            int left = height[i];
            int right = height[i];
            //找左边最高的
            for(int l = i - 1;l >= 0;l--){
                if(height[l] > left){
                    left = height[l];
                }
            }
            for(int r = i + 1;r < height.length;r++){
                if(height[r] > right) {
                    right = height[r];
                }
            }
            //记录当前能积攒的雨水
            int h = Math.min(left,right) - height[i];
            if(h > 0) sum += h;
        }
        return sum;
    }
}

0 赞同 0 条回复

【动态规划专题】LeetCode 42. 接雨水

共以下 10 个回答

双指针，巧妙避开DP

# 回答此问题取消回复

【动态规划专题】LeetCode 42. 接雨水

共以下 10 个回答

双指针，巧妙避开DP

# 回答此问题 取消回复

# 回答此问题取消回复