Leetcode11:盛水最多的容器——双指针
目录
题目
https://leetcode-cn.com/problems/container-with-most-water/
每次看题解：“我又会了！”
下一题：“我是废物。”
题解
双指针
定义两个指针left和right分别在最左边和最右边，指向两个柱子，那么面积肯定等于两柱子中最小的柱子乘上宽度。
求出面积后要移动指针，那么移动哪一个指针呢？当然是指向柱子中较矮的那个指针。因为如果移动高的珠子，宽度减小，而由于短板效应，高度仍取决于矮柱子，所以移动后的面积只减不增。
那如果两指针指向柱子的高度相同呢？那就两个指针一起向中间移动，原理同上。
代码：
class Solution {
public:
int maxArea(vector<int>& height) {
int max_area = 0;
int left=0,right=height.size()-1;
while(left<right){
if(height[left]<height[right]){
max_area = max(max_area, height[left]*(right-left));
left++;
}
else if(height[left]>height[right]){
max_area = max(max_area, height[right]*(right-left));
right--;
}
else{
max_area = max(max_area, height[left]*(right-left));
left++;
right--;
}
}
return max_area;
}
};
相比于暴力搜索，这种方法相当于是剪枝，把不可能的情况都嘎掉了。
时间复杂度O(n)，空间复杂度O(1)。