查阅更多的题解,请点击
Problem
Solution
two pointer, O(n) time, O(1) space
按照解决问题的一般套路(参考算法笔记(一)概述):观察问题能不能reduce:输入数据为数组,按照常见的方式无法reduce;则考虑观察解空间,先给出一个解,再逐步优化到最优解。
最容易得到的一个结果是:数组第一个元素作为container的左边界,最后一个元素作为右边界,那么container的高为min(左边界,右边界)
- 左边界的优化策略:只有当左边界大于上一个解的高时,有可能得到更好的解
- 右边界的优化策略:只有当右边界大于上一个解的高时,有可能得到更好的解
- 约束条件:左右边界相遇停止
class Solution
{
public:
int maxArea(vector<int> &height)
{
int i = 0, j = height.size() - 1, water = 0;
while (i < j)
{
int h = min(height[i], height[j]);
water = max(water, (j - i) * h);
while (height[i] <= h && i < j)
i++;
while (height[j] <= h && i < j)
j--;
}
return water;
}
};