力扣42.接雨水

力扣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;}};