42.收集雨水（Trapping Rain Water）
方法一：利用双指针交叉循环求解，时间复杂度O(n)
//接雨水
int trap(vector<int>& height) {
int i=0,j=height.size()-1;
int left_max=0,right_max=0;
int van=0;
while(i<j)
{
if(height[i]<height[j])
{
if(height[i]>left_max)
{
left_max=height[i];
i++;
}
else
{
van+=left_max-height[i];
//第一次漏掉了i++
i++;
}
}
else
{
if(height[j]>right_max)
{
right_max=height[j];
j--;
}
else
{
van+=right_max-height[j];
j--;
}
}
}
return van;
}
方法二：动态规划O(n)
int trap(vector<int>& height) {
//动态规划,事先保存
int n=height.size();
vector<int> left_max(n);
vector<int> right_max(n);
int max=0;
for(int i=0;i<n;i++)
{
if(height[i]>=max)
{
max=height[i];
}
left_max[i]=max;
//i++; 已经加过了
}
max=0;
for(int j=n-1;j>=0;j--)
{
if(height[j]>=max)
{
max=height[j];
}
right_max[j]=max;
//j-- ;
}
int ans=0;
for(int i=0;i<n;i++)
{
if(height[i]<left_max[i]&&height[i]<right_max[i])
{
//理解出错
ans+=min(left_max[i],right_max[i])-height[i];
}
}
return ans;
}
标签：right,van,int,max,height,left,随笔,leetcode,刷题 From： https://www.cnblogs.com/lzuu/p/17331734.html