双指针降低问题复杂度的维数

11. 题目链接-来源：力扣（LeetCode）（中等）

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

思路：

本质上就是求n块板子两两配对，它们之间的长度和距离所围成的矩形面积。如果暴力解，每块板子都与剩下的n-1块板子配对计算一次面积，也不是不行，但是复杂度为O(n²)，太笨了。
简化问题，首先面积 = 距离 * 高度，距离好办，我们一开始分别选择两侧的板子就能保证距离最远。高度呢，那就逐渐缩短距离，以距离换高度。
那么从哪边开始缩呢，根据短板原理，需要先改变较低的一边，否则水位只可能下降（另一侧变得比这一侧还要矮）或者持平（另一侧变高或者不变）。所以确定好距离收缩的规则，从两侧向中间收缩，每次收缩求出面积取最大值即可。
时间复杂度：O(n)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int left = 0;
        int right = n - 1;
        int ans = 0;
        while (left < right) {
            int leftHeight = height[left];
            int rightHeight = height[right];
            ans = Integer.max(ans, Integer.min(leftHeight, rightHeight) * (right - left));
            if (leftHeight <= rightHeight) {
                left++;
            } else {
                right--;
            }
        }
        return ans;
    }
}