yicong@algo: ~/code/02-two-pointers/0011-container-with-most-water.cpp

yicong@algo:~/code/02-two-pointers$ cat 0011-container-with-most-water.cpp

11. 盛最多水的容器

中等 双指针 题目 ↗ 源码 ↗

// 思路

左右指针从两端往中间收。每轮算当前面积,然后移动较矮的那一侧; 宽度必然减 1,想让面积变大只能指望遇到更高的板子。

// 时间复杂度

O(n),两个指针合计最多走 n 步

// 空间复杂度

O(1)

// 易错点

必须移动「较矮」的一侧;面积 = min(height[l], height[r]) * (r - l)

// 面试口述要点

为什么放弃矮板不会漏掉最优解——若保留矮板而移动高板, 宽度变小且高度上限仍是那块矮板,面积只会更小,所以移动矮板是唯一可能变好的选择

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = (int)height.size()-1;
        int ans = 0;
        while (left < right) {
            ans = max(ans, min(height[left], height[right]) * (right - left));
            if (height[left] < height[right]) ++left;
            else                              --right;
        }
        return ans;
    }
};

// 本地测试:输入 n,然后 n 个高度;输出最大水量
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<int> height(n);
    for (int& x : height) cin >> x;

    cout << Solution().maxArea(height) << '\n';
    return 0;
}