题目:
题解:
第一种可行的方案:
设置左指针指向第一条线,设置右指针指向最后一条线。每次向中间移动两条线中最短的一条,计算移动过程中最大接水量。
本题可以看出影响接水量的有两个因素,两条线的距离,两条线的最短长度。所以只单独考虑其中一个式可行的,该解法相当于固定了或者说是单向改变,两条线之间的距离因为两条线离得越远越可能接更多的水,所以从最远距离开始考虑或者可以说是枚举,从大到小的每个距离在另一个两条线最短的最优情况。
int maxArea(vector<int>& height) {
int r=height.size()-1,l=0;
int ans=0;
while(l<=r){
ans=max(min(height[r],height[l])*(r-l),ans);
if(height[r]<height[l])r-=1;
else l+=1;
}
return ans;
}
时间复杂度:O(n)
空间复杂度:O(1)
题后反思:
这题做到最后好像是一种枚举的思想比平常使用的更高一维,有两个变量找最大值,可以让其中一个条件单调变换,然后再在其中找到另一个调节的最优情况,在这过程中找到最优解。