11.盛最多水的容器

Problem: 11. 盛最多水的容器

思路

本题采用双指针的思路。

一开始我尝试了动态规划，但是发现难以构建最优子结构。
然后我也试着用双指针，但是对于双指针的理解还不够，所以没有想到双指针也可以从数组的两端开始，相向移动。

双指针最重要的是要维护一个区间信息。当我们把指针从数组的两边移动时，可以维护一个什么信息？

这个区间里的的所有的点都可以作为容器的边界。换言之，区间外的点就不值得作为容器边界尝试了。

我们每次都移动高度较小的指针，因此我们这里需要证明，这个高度较小的指针不再可能作为容器的边界，产生一个更高的答案值了。

如果我们不移动这个高度较小的指针，而把它作为左边界，从而右指针可以取小于等于右边界的任何值。首先横轴的距离在不断减小，其次由于左指针的值小于等于右指针的最初的值，以为着容器的盛水高度在右指针最初时就已经达到了理论最大值（左指针的值），移动右指针已经无用。因此，我们证明了左指针的位置已经不再可能产生更高的盛水量，左指针可以向右移动。

双指针理解

从这题我们可以看出，双指针，尤其是相向双指针，其很大一个作用是进行搜索的剪枝。我们利用题目性质排除了不可能的点，因此可以把时间复杂度从$O(N^2)$降低到$O(N)$。接着做双指针的题目，再来继续强化理解。

Code

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int l = 0;
        int r = n - 1;
        int ans = 0;
        while (l <= r) {
            ans = Math.max((r - l) * Math.min(height[l], height[r]),ans);
            if (height[l] < height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return ans;
    }
}