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

hi 普通 2023年12月15日下午11:44

两个数组保存每个位置上左边和右边的最大值

class Solution {
public:
    int trap(vector<int>& height) {
        //循环高度数组中的每个元素，判断此位置能不能接雨水，如果能接，可以接多少？
        //看该位置左边 和 右边 的最高高度分别是多少，如果某一边的高度比该位置自己的位置还低，那肯定是存不了雨水的，如果比自己的高度高，那么取决于小的那一边（有点木桶效应的意思）
        int n = height.size();
        vector<int> leftmax(n); //定义数组长度，不然后面访问leftmax[i] 会出错
        vector<int> rightmax(n);
        int res = 0;

        leftmax[0] = 0;
        for(int i = 1; i < n; i++)     leftmax[i] = max(height[i - 1], leftmax[i - 1]);

        rightmax[n - 1] = 0;
        for(int i = n - 2; i >= 1; i--) rightmax[i] = max(height[i + 1], rightmax[i + 1]);

        for(int i = 1; i <= n - 2; i++) res += max(0, min(leftmax[i], rightmax[i]) - height[i]);

        return res;
    }
};

双指针动态记录每个位置左边和右边的最大值

class Solution {
public:
    int trap(vector<int>& height) {      
        int  n = height.size();
        int i = 0, j = n - 1, maxl = height[0], maxr = height[n - 1], res = 0;  
    //双指针解法: 通过两个指针寻找当前位置下左右分别最高的方块数、用两个变量存储，代替leftmax 和rightmax 数组，节省空间
    //指向位置上左右有更小方块数一边的指针向后移动，那么当前maxl 或 maxr 存的一定是当前位置左右的最大方块数
    //指针指向该位置就可以计算了，是因为最后看该位置能存多少雨水是看小的那一边min(mal, maxr)，我指针移动到该位置了证明上一次比较出来了更小的值，不用管另一边最大值具体为多少，因为我更小以后答案肯定是以我为准
        while(i < j){
            if(maxl <= maxr){
                i++;
                res += max(0, maxl - height[i]);
                maxl = max(maxl, height[i]);
            }else{
                j--;
                res += max(0, maxr - height[j]);
                maxr = max(maxr, height[j]);
            }
        }

        return res;
    }
};

0 赞同 0 条回复

June 普通 2023年11月15日下午5:13

class Solution {
public int trap(int[] height) {
if(height.length 0)
return 0;
int n = height.length;
int left = 0, right = n-1;
int ans = 0;
int l_max = height[0];
int r_max = height[right];

    while(left <= right)
    {
        l_max = Math.max(l_max,height[left]);
        r_max = Math.max(r_max,height[right]);

        if(l_max <= r_max) // 这时不管右边多高，这一列能装的水只取决于l_max
        {
            ans += l_max - height[left];
            left++;
        }
        else
        {
            ans += r_max - height[right];
            right--;
        }
    }
    return ans;
}

}

0 赞同 0 条回复

Marshan 普通 2023年9月4日上午10:19

做了好几次这次还是忘了,明明会

class Solution {
public:
    int trap(vector<int>& height) {
        // 简化问题就只考虑height[i]能接的雨水
        // ans = max(height[i],min(lmax,rmax)) - height[i];
        int n = height.size();


        int lmax = height[0];
        int rmax = height[n-1];
        int left = 0;
        int right = n - 1;

        int ans = 0;

        while(left <= right){
            lmax = max(height[left],lmax);
            rmax = max(height[right],rmax);

            if(lmax < rmax){
                ans += lmax - height[left];
                left++;
            }
            else{
                ans += rmax - height[right];
                right--;
            }
        }

        return ans;
    }
};

0 赞同 0 条回复

北辰普通 2023年8月25日上午10:54

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

时间复杂度:O（n)
空间复杂度：O（n）

0 赞同 0 条回复

人生何处不青山普通 2023年8月21日下午11:45

常规题

function trap(height: number[]): number {
    let prev = new Array(height.length);
    let last = new Array(height.length);
    let res = 0;
    prev[0] = height[0];
    for (let i = 1; i < height.length; i++) {
        prev[i] = Math.max(prev[i - 1], height[i]);
    }
    last[height.length - 1] = height.slice(-1)[0];
    for (let i = height.length - 2; i >= 0; i--) {
        last[i] = Math.max(height[i],last[i+1]);
    }
    for(let i = 0; i < height.length; i ++ ) {
        res += Math.min(prev[i],last[i]) - height[i];
    }
    return res;
};

0 赞同 0 条回复

Mby 普通 2023年8月21日下午4:48

class Solution {
    //双向指针
    //以最短的柱子来计算，从两边往中间遍历
    public int trap(int[] height) {
        int res = 0;
        int l = 0, r = height.length - 1;
        int pre_max = height[l];
        int suf_max = height[r];

        while(l < r){
            pre_max = Math.max(pre_max, height[l]);
            suf_max = Math.max(suf_max, height[r]);

            if(pre_max < suf_max){
                res += pre_max - height[l];
                l ++;
            }else{
                res += suf_max - height[r];
                r--;
            }
        }
        return res;
    }
}

0 赞同 0 条回复

AD钙奶普通 2023年8月11日下午3:27

相向双指针
木桶效应，以短的木板来计算实际水量，两边一起往中间遍历

class Solution {
    public int trap(int[] height) {
        int res = 0;
        int l = 0, r = height.length - 1;
        int pre_max = height[l];
        int suf_max = height[r];

        while(l < r) {
            pre_max = Math.max(pre_max,height[l]);
            suf_max = Math.max(suf_max,height[r]);

            if(pre_max < suf_max) {
                res += pre_max - height[l];
                l ++;
            } else {
                res += suf_max - height[r];
                r --;
            }
        }
        return res;
    }
}

0 赞同 0 条回复

阿尚普通 2023年8月9日下午11:28

//方法一：双指针
class Solution {
    public int trap(int[] height) {
        if(height.length == 0){
            return 0;
        }

        int[] lmax = new int[height.length];//记录左边第一个比当前位置高的柱子
        int[] rmax = new int[height.length];//记录右边第一个比当前位置高的柱子
        lmax[0] = height[0];
        rmax[height.length - 1] = height[height.length - 1];

        for(int i = 1; i < height.length; i++){
            lmax[i] = Math.max(height[i], lmax[i - 1]);
        }
        for(int i = height.length - 2; i >= 0; i--){
            rmax[i] = Math.max(height[i], rmax[i + 1]);
        }

        int result = 0;
        for(int i = 0; i < height.length; i++){
            result += Math.min(lmax[i], rmax[i]) - height[i];//统计总雨水量
        }

        return result;
    }
}

//方法二：单调栈
class Solution {
    public int trap(int[] height) {
        int result = 0;
        Deque<Integer> stack = new ArrayDeque<>();//单调栈：维护从栈底到栈顶高度递减
        stack.push(0);

        for(int i = 1; i < height.length; i++){
            while(!stack.isEmpty() && height[i] > height[stack.peek()]){
                int temp = stack.pop();
                if(!stack.isEmpty()){
                    int h = Math.min(height[i], height[stack.peek()]) - height[temp];
                    int w = i - stack.peek() - 1;
                    result += h * w;
                }
            }
            stack.push(i);
        }

        return result;
    }
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年8月9日上午8:42

8.8 周二
Day29：下面是代码

class Solution {
    public int trap(int[] height) {
        //动态规划，对方法二的优化。使时间复杂度从On2降低到On
        int sum = 0;
        int n = height.length;
        int[] max_left = new int[n];
        int[] max_right = new int[n];
        for(int i = 1; i < n - 1; i++){
            max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
        }
        for(int i = n - 2; i >= 0; i--){
            max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
        }
        for(int i = 1; i < n - 1 ; i++){
            int min = Math.min(max_left[i], max_right[i]);
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }
        }
        return sum;
    }
}

0 赞同 0 条回复

NullPointerException 普通 2023年8月8日下午7:33

class Solution {
public int trap(int[] height) {
///通过列计算找到每列左右的最高墙左右最高找里面最小的那个座位短板
//1.如果当前列<短板可以存水
//2. >=短板无法存水
int maxleft[]=new int[height.length];
int maxright[]=new int[height.length];
maxleft[0]=height[0];
int sum= 0;
for(int i=1;i<height.length;i++)
{
maxleft[i]=Math.max(maxleft[i-1],height[i]);
}
maxright[height.length-1]=height[height.length-1];
for(int i=height.length-2;i>=0;i–)
{
maxright[i]=Math.max(maxright[i+1],height[i]);
}
for(int i=1;i<height.length-1;i++)
{
if(height[i]<Math.min(maxleft[i],maxright[i]))
{
sum=sum+Math.min(maxleft[i],maxright[i]) – height[i];
}
}
return sum;
}
}

0 赞同 0 条回复

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

共以下 10 个回答

# 回答此问题取消回复

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

共以下 10 个回答

# 回答此问题 取消回复

# 回答此问题取消回复