【力扣hot100题】(004)盛水最多的容器
现在能这么快做出来纯粹是因为当时做的时候给我的印象实在太深了。
犹记得这题是当年开启我用CSDN记录leetcode日记历史的开端。
总之印象太深了不会都不行啊!!记得当年是想到用各种动态规划回溯等等等等最终发现是最简单贪心和双指针。
解法也是非常简单,使用双指针,因为水桶装的水取决于最短的那块木板,所以每次只要前移最短的那块板子,一直移动到比当前这块板子大,反反复复。
每次移动完就比较一下最终结果。
class Solution {
public:
int maxArea(vector<int>& height) {
int front=0;
int back=height.size()-1;
int result=0;
while(front<back){
result=max(result,(back-front)*min(height[front],height[back]));
if(height[front]<height[back]){
int x=front+1;
while(x<back&&height[x]<height[front]) x++;
front=x;
}
else{
int x=back-1;
while(x>front&&height[x]<height[back]) x--;
back=x;
}
}
return result;
}
};