11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

n == height.length
2 <= n <= 10⁵
0 <= height[i] <= 10⁴

较暴力的逻辑

对于前面的每一条线 \(i\)，能构成盛最多水的容器的另外一条线肯定是离它越远越好，这样的话，该容器的宽就会被拉长；

但也并不是宽越长，离它越远，盛的水就越多，还得看最后面的那几条线的高度如何，若最后一条线高于前面的线 \(i\) ，那么与 \(i\) 构成盛最多水的容器的另外一条边，绝对就是这条边；

但实际情况下，比这更复杂，我们先从后面往前找到比 \(i\) 高或等的线 \(j\) ，则 \(i \sim j\) 之间能与 \(i\) 构成盛最大水量的容器必定是 \(j\) 线；

但对于 \(j \sim n\) 之间的线，由于宽度增加了，虽然高度有些许下降，但我们还得遍历一遍 \(j \sim n\) 之间的线，才能确定最大盛水量。

时间复杂度 \(O(n^2)\) 代码参考

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = 0;
        for (int i = 0; i < height.size(); i ++)
        {
            for (int j = height.size() - 1; ;j --)
            {
                res = max(res, (j - i) * min(height[i], height[j]));
                if (height[j] >= height[i]) break;
            }
        }
        return res;
    }
};

11. 盛最多水的容器

较暴力的逻辑

双指针