LeetCode 11. 盛最多水的容器

盛最多水的容器

给定一个长度为 n$(n==height.length,2<=n<=10^5)$ 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) $(0<=height[i]<=10^4)$ 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。相关标签：贪心, 数组, 双指针。

Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the $i^{th}$ line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container. Related Topics: Array, Two Pointers, Greedy.

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
1
2
3

Input: height = [1,1]
Output: 1
1
2

题意是假设有一个二维平面，这个二维平面上面一共有很多的柱子，就是每个整点坐标上面会有很多竖线，然后我们要从中挑两条竖线，两条竖线会形成一个凹槽，那么我们往这个凹槽里面倒水的话，倒到两根线中短的那根线的时候就满了再多倒的话酒倒出来了。那我题目希望我们求什么呢？希望让我们求选哪两条竖线会使得我们倒的水的总面积最大。题目输入是一个数组，下标的话就是它的横坐标，数组的值就是它的高度，相当于就是告诉了我们很多柱子的位置和高度，然后问我们怎么选可以使得总面积最大。

这个题属于脑经急转弯的类型很难而且思维具有跳跃性，如果直接想的话其实不是很容易想。但是也有一些通法是可以做的，比如说可以用单调队列和单调栈来做，但是这样的话会特别麻烦。

像这样思维题还是直接讲做法比较好因为它的思维具有跳跃性是很难直接推理出来，先来说下常规的做法是怎么样的。有很多柱子，我们用两个指针，一个指向最开头，一个指向结尾。然后每次比较一下这两个指针指向的柱子的高度：如果说第二个指针指向的高度比较低的话，那么我们就把第二个指针往前移动一位；如果说第一个指针指向的高度比较低的话那么我们就把第一个指针往后移动一位。然后每移完一次我们求一下当前两个指针指向的高度它们所组成的面积是多少，面积就是它们两个高度较低的那个高度乘以它们的距离就可以了，然后更新一下最大值就可以了。

这个其实就是一个双指针做法，这个做法比较简单，但是比较复杂的是要考虑一下这个做法为什么是正确的，为什么我们这种做法是一定可以求到最优解的？我们来证明一下，证明其实比较形象。假设最优解是某两根柱子，我们两根指针最开始是在这两个柱子的两侧，每次是把某一个指针向中间靠拢一点，那么必然会出现什么情况呢？就是这两个指针必然会有一个指针先到这个最优解的某一边，要么是左边先到要么是右边先到反正一定是有一边先到的。那么我们不妨设左边先到，我们左边到这个柱子的时候那么我们右边这个指针还在比较远的位置对吧。那么我们现在来证明什么呢？我们先来证明如果说左边先到达最优解的边界的话那么我们右边这个指针指向的这个竖线的高度在左移的时候每次都严格小于左边指针指向的最优解竖线高度。就是只要我们左边到达了最优解的边界那么我们右边会一直往左移直到移到右边最优解的位置上去，只要能证明这点的话就能我们就可以证明我们这个做法是一定可以把这个最优解找出来的。因为对于任意一个最优解，我只要有一边达到边界，那么另外一边一定会向这个边界不断靠拢，这样的话就可以证明出来我们一定会把这个边界选到。

那么我们来看一下为什么这样是正确的？我们接下来用反证法证明，假设我们左边先到达这个边界，右边的这个高度是大于等于左边的。那么会有什么矛盾呢？由于右边是大于左边，此时它们两个指向的区域的灌水面积就是右边非最优解的竖线和左边最优解围成的面积，而右边最优解的线最好的情况也就是比左边最优解的竖线更高或者一直往上延伸，也就是说面积完全由左边的最优解竖线高度和左边与右边的某根线的距离决定。此时右边指针还没有到达最优解。则显然它与左边最优解的距离大于右边最优解与左边最优解的距离，那就与右边最优解与左边最优解围成的面积才是最大值相矛盾了。所以我们可以得到结论，假如只要我们左边最先到达最优解边界，那么我们右边指针此时指向的高度是严格小于左边界的，就意味着我们右边的指针会一直往左边走，直到走到最优解的位置为止，所以任意一个最优解都一定可以遍历到，那么我们最后这两个指针取得的最大值就是我们的最优解。这题其实还是属于贪心题更多一点。

时间复杂度：两个指针总共扫描 n 次，因此总时间复杂度是 O(n)；空间复杂度：O(1)，只需要额外的常数级别的空间。

然后是代码怎么写：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res=0;
        for(int i=0,j=height.size()-1;i<j;) {
            res=max(res,min(height[i],height[j])*(j-i));
            if(height[i]>height[j]) j--;
            else i++;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

func maxArea(height []int) int {
    res:=0
    for i,j:=0,len(height)-1;i<j; {
        res=max(res,min(height[i],height[j])*(j-i))
        if height[i]>height[j] {
            j--
        } else {
            i++
        }
    }
    return res    
}

func max(x,y int) int {
    if x>y {
        return x
    }
    return y
}

func min(x,y int) int {
    if x>y {
        return y
    }
    return x
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26