查阅更多的题解，请点击

Problem

11. Container With Most Water

Solution

two pointer, O(n) time, O(1) space

按照解决问题的一般套路（参考算法笔记（一）概述）：观察问题能不能reduce：输入数据为数组，按照常见的方式无法reduce；则考虑观察解空间，先给出一个解，再逐步优化到最优解。

最容易得到的一个结果是：数组第一个元素作为container的左边界，最后一个元素作为右边界，那么container的高为min(左边界，右边界)

• 左边界的优化策略：只有当左边界大于上一个解的高时，有可能得到更好的解
• 右边界的优化策略：只有当右边界大于上一个解的高时，有可能得到更好的解
• 约束条件：左右边界相遇停止

GitHub传送门

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