11-container with most water.md

题意

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

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

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

说明：你不能倾斜容器。

解法

还是老规矩，我们先来看下数据范围。这里n的最大范围是1e5，那么很明显，我们基本上可以排除掉$O(n\log n)$复杂度以上的算法了。至少暴力枚举估计是不行了。

看完数据范围之后我们来分析题目，题面很简单，就是要求一个最大的横截面积。我们来分析一下这个面积的组成，很容易发现，它一定是一个矩形。它的长是两个挡板之间的距离，宽是两个挡板当中短的那个长度。我们要做的就是找到这样的挡板，使得它们围成的矩形面积最大。

如果我们直接苦思冥想去思考怎么样找到这样的挡板对，可能会比较复杂，有一种无从下手的感觉。因为我们前面已经排除掉了暴力的方法，直接枚举一定会超时。这个时候就需要我们先停下来，思考一下曲线救国的途径了。

想要曲线救国还是要先回到题目当中来，先来分析一下题意。我们都知道矩形的面积取决于长和宽，如果长和宽都增大，那么面积一定增大。如果长和宽一个增大一个减小，矩形的面积有可能增大也有可能减小。在本题当中，矩形的宽最大是已知的，就是n-1。对于宽最大的情况来说，矩形的长也是已知的，就是max(height[0], height[n-1])。

无论我们再怎么寻找，我们都不可能找到宽更长的矩形，所以要使得矩形面积更大的话，必须要有更长的长边。而长边取决于两个挡板当中较短的一个，所以我们很自然可以想到，对于一个已知的矩形，我们想要寻找更大面积的可能，只需要固定其较长的边，对于较短的边则往内部遍历寻找更长的边。如果能够找到更长的边，就说明矩形的面积存在增大的可能。

我们依次更新两边的隔板，维护最大面积即可。

class Solution {
public:
    int maxArea(vector<int>& height) {
        // 左侧挡板从0开始，右侧挡板设置成n-1
        int l = 0, r = height.size()-1;
        int ret = min(height[l], height[r]) * (r-l);
        while (l < r) {
            // 如果左侧挡板更小
            if (height[l] < height[r]) {
                // 则左侧挡板往内移动
                while (l < r && height[l] < height[r]) {
                    l++;
                    ret = max(ret, min(height[l], height[r]) * (r-l));
                }
            // 如果右侧挡板较小
            }else {
                while (l < r && height[l] >= height[r]) {
                    r--;
                    ret = max(ret, min(height[l], height[r]) * (r-l));
                }
            }
        }
        return ret;
    }
};