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