力扣(LeetCode)11. 盛最多水的容器(C++)

双指针+贪心

盛水的面积 = 长度 $\times$ 左右柱子最低高度
$area=(r-l)\times min(height[l],height[r])$
初始时，我们不知道每个柱子的高度，但是我们可以选取最左侧柱子和最右侧柱子，使得 $(r-l)$ 最大。乘数的另一项，取决于左右柱子的最低值，选取左右柱子较低的那一根，向中间移动，移动时 $(r-l)$ 减小， $min(height[l],height[r])$ 可能增大，也就是 $area$ 可能增大。这是本题的贪心思路。

代码展示

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans = 0;
        for(int l = 0,r = height.size()-1;l<r;){
            int area = min(height[r],height[l]) * (r-l);
            ans = max(ans,area);
            if(height[l]<height[r]) l++;
            else r--;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度 $O(n)$ ， $n$ 是柱子的数量，最多遍历一次找到最大面积，时间复杂度 $O(n)$。

空间复杂度 $O(1)$ ， 除若干变量使用的常量级空间，没有使用额外的线性空间 。

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC