网站链接: element-ui dtcms
当前位置: 首页 > 技术博文  > 技术博文

每日一题DAY3直方图的水量

2021/4/2 22:34:50 人评论

直方图的水量 动态规划 双指针 直观上每个位置的储水量 min(左边最高,右边最高) - 当前高度 (算式1) 1.动态规划分别计算出每个点左端最高和右端最高,两次循环; 第三次循环按算式1计算结果; 时…

直方图的水量
动态规划 双指针
直观上每个位置的储水量 = min(左边最高,右边最高) - 当前高度 (算式1)
1.动态规划分别计算出每个点左端最高和右端最高,两次循环;
第三次循环按算式1计算结果;
时空都是O(n)


class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0)
            return 0;
        vector<int> left(n,0);
        vector<int> right(n,0);
        left[0] = height[0];
        for(int i=1;i<n;++i)
            left[i] = max(left[i-1],height[i]);
        right[n-1] = height[n-1];
        for(int i=n-2;i>=0;--i)
            right[i] = max(right[i+1],height[i]);
        //
        int res = 0;
        for(int i=0;i<n;++i)
            res+=min(left[i],right[i]) - height[i];
        return res;
    }
};

2.优化left,right数组
在算式1中min(lmax,rmax)可以看到,真正有用的是小值;
双指针l,r指向两端
如果对于某一点,我知道它真正的lmax,看到了一部分的rmax,这个rmax已经比lmax大了,那么该点rmax(真) >= rmax(当前更新) > lmax,储水量将由lmax确定;
右侧同理
时空O(1)

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0)
            return 0;
       int lmax = height[0],rmax = height[n-1];
       int res = 0;
       int l = 0,r = n-1;
       while(l <= r){
           if (lmax < rmax){
               lmax = max(lmax,height[l]);
               res+=lmax - height[l];
               ++l;           
           }
           else{
               rmax = max(rmax,height[r]);
               res+=rmax - height[r];
               --r;  
           }
       }
        return res;
    }
};

相关资讯

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?