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;
}