力扣42.接雨水C++解法

法一 按列求

主要参考了@windliang的java题解，写了下C++的

42. 接雨水 - 力扣（Leetcode）

320/322个样例

超出时间限制

class Solution { public:int trap(vector<int>& height) {int res=0;int n=height.size();for(int i=0;i<n;i++){int lmax=0,rmax=0;for(int j=0;j<i;j++)if(height[j]>lmax) lmax=height[j];for(int k=i+1;k<n;k++)if(height[k]>rmax) rmax=height[k];if(height[i]>=rmax||height[i]>=lmax)continue;res=res+(lmax>rmax ? (rmax-height[i]) : (lmax-height[i]));}return res;} };

法二 动态规划

class Solution { public:int trap(vector<int>& height) {int res=0;int n=height.size();vector<int> lmax_tall(n,0);vector<int> rmax_tall(n,0);for(int i=1;i<n;i++){lmax_tall[i]=max(lmax_tall[i-1],height[i-1]);}for(int j=n-2;j>=0;j--){rmax_tall[j]=max(rmax_tall[j+1],height[j+1]);}for(int k=1;k<n-1;k++){if(height[k]>=rmax_tall[k]||height[k]>=lmax_tall[k])continue;res=res+(lmax_tall[k]>rmax_tall[k] ? (rmax_tall[k]-height[k]) : (lmax_tall[k]-height[k]));}return res;} };

需要新开两个On数组

法三 双指针

本题关键是求min的值，即在左右高度最高的值两者中取较小的

min=min(max_left,max_right) max_left=max(left-1的高度，left-1左边最大的值) max_right=max(right+1的高度，right+1右边最大的值)

由此画图可知已知右方有个高值时，只用考虑左边情况，左方有高值时只用考虑右边，由此用双指针遍历一次即可

时间复杂度： O(n)

空间复杂度： O(1)

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

总结

以上是生活随笔为你收集整理的力扣42.接雨水C++解法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。