当前位置: 首页> 房产> 市场 > 力扣42.接雨水

力扣42.接雨水

时间:2025/7/9 2:33:06来源:https://blog.csdn.net/Pisasama/article/details/139881676 浏览次数:0次

力扣42.接雨水

前后缀数组

  • 对于每个一个位置

    • 求其前面最高高度pre_max[i] = max(pre_max[i-1] , h[i])
    • 和后面最高高度suf_max[i] = max(suf_max[i+1] , h[i])
    • 当前i处的水容量 为min(pre_max[i] , suf_max[i]) - h[i]
  •   class Solution {public:int trap(vector<int>& height) {int n = height.size();vector<int> pre_max(n),suf_max(n);pre_max[0] = height[0];suf_max[n-1] = height[n-1];for(int i=1;i<n;i++)pre_max[i] = max(pre_max[i-1],height[i]);for(int i=n-2;i>=0;i--)suf_max[i] = max(suf_max[i+1],height[i]);int res=0;for(int i=0;i<n;i++)res += min(pre_max[i],suf_max[i]) - height[i];return res;}};
    

双指针

  • 考虑不用数组存pre_max和suf_max而改用实时更新

    • 每到达一个位置时 更新pre_max和suf_max
    • 若pre_max < suf_max 说明当前水容量为 pre_max(小的) - h[i]
    • 反之亦然
  •   class Solution {public:int trap(vector<int>& height) {int n = height.size();int l = 0,r = n-1;int res=0;int pre_max = 0,suf_max = 0;while(l <= r){pre_max = max(pre_max,height[l]);suf_max = 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;}};
    
关键字:力扣42.接雨水

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: