11. 盛最多水的容器

首先想到的就是暴力算法，遍历整个二维数组，将i与i-1…i-n依次求值，求得最大值。此算法时间复杂度为O(n^2)，空间复杂度为O（1）。

那么有没有办法降低时间复杂度呢？

这个题如果第一次做，想不到解法很正常，只能靠一些过去的刷题经验，即这样的数组问题通常使用双指针解决。

class Solution {
    public int maxArea(int[] height) {
        int result = 0;
        int left = 0;
        int right = height.length-1;
        while (left < right) {
            int h = Math.min(height[left], height[right]);
            int area = (right-left)*h;
            result = Math.max(result, area);
            if (height[left] > height[right]) {
                right--;
            } else {
                left++;
            }
        }
        return result;
    }
}

算法思想是这样的，定义left、right两个指针，从数组的两端往中间收缩，面积计算完成后，总是移动高度较低的那个指针。

我最开始想不明白为什么是移动高度较低的那个指针？这里我们假设height[left] < height[right]

因为area = Min(h[right], h[left]) * (right - left)，如果我们移动right，接下来新容器的底变小了，且新容器的高h’< h[left]（因为高度取决于最小高度），那么必然不可能找到比当前更大的面积。所以我们只能移动高度角度的那个指针，这样才有可能在底变小的同时，或许能够找到比h[right]更大的h[right]'以抵消底变小的面积损失。