LeetCode 11. 盛最多水的容器 C++ 实现
核心思路：双指针贪心，左右指针从两端向中间收缩，每次移动高度更小的指针，时间复杂度 O(n)，空间 O(1)。
cpp
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
int max_area = 0;
while (left < right) {
int h = min(height[left], height[right]);
int w = right - left;
max_area = max(max_area, h * w);
// 移动较矮的一侧，才有可能得到更大面积
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return max_area;
}
};
原理说明
1. 容器面积由较短的柱子高度和两柱间距决定；
2. 若移动高的指针，宽度减小、高度不会变大，面积一定变小；
3. 只有移动矮的指针，才有可能获得更高的高度，从而得到更大面积；
4. 左右指针不断向中间靠拢，遍历一次即可得到最大值。
测试用例
cpp
#include <iostream>
int main() {
Solution sol;
vector<int> h1 = {1,8,6,2,5,4,8,3,7};
cout << sol.maxArea(h1) << endl; // 49
vector<int> h2 = {1,1};
cout << sol.maxArea(h2) << endl; // 1
return 0;
}
复杂度：
- 时间：O(n)，仅一次遍历
- 空间：O(1)，常数额外空间
