LeetCode11. Container With Most Water（对撞指针）

Medium
Accepted：305,268
Submissions：728,193

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

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.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

链接

https://leetcode.com/problems/container-with-most-water/

题意

给定一个包含n个非负整数的数组，每个数构成一个点(i, a[i])，点(i, a[i])和点(i, 0)之间形成一条线段，找两条线段使它们与x轴之间构成的容器能装最多的水。

题解

暴力解法就两层循环，时间复杂度$O(n^2)$
使用对撞指针l和r，初始时l指向头，r指向尾，答案肯定是ans = max(ans, (min(height[l], height[r]) * (r - l)));但问题是如何更新l和r呢？
首先我们确定下，容器的“面积”取决于两条线段中更短的那条以及线段之间的距离。
然后对于两条线段，如果height[l] < height[r]，即左侧线段比右侧线段短，那么a[l]与右侧的线段就不用考虑了，因为这时的最大值肯定是height[l]*(r-l)，所以只需更新l让l++，而r不变；同理当height[l] < height[r]只需更新r让r--，而l不变，等于时均适用。
这样只需一次遍历就可以找到答案，时间复杂度为$O(n)$。
一个更为直观的解释可以参考LeetCode上kongweihan发的一个讨论，应该比较容易看懂，文末附上。
举个例子，对于1 8 6 2 5 4 8 3 7，a[l]=1 < a[r]=7，此时1只能与最右边的7产生最大值，所以对于1而言，右边除了7的其他值都是没用的；更新a[l]=8 > a[r]=7，此时7只能与左侧的8产生产生最大值，对于7而言，左侧除了8的其他值都是没用的，以此类推。（其中1和7代表着更短的那条线段）

代码

Runtime: 12 ms, faster than 98.51% of C++ online submissions for Container With Most Water.
Memory Usage: 1.3 MB, less than 52.48% of C++ online submissions for Container With Most Water.

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int ans = 0;
        while (l < r)
        {
            ans = max(ans, (min(height[l], height[r]) * (r - l)));
            if (height[l] < height[r])
                l++;
            else
                r--;
        }
        return ans;
    }
};

The end.
2019年2月4日星期一

解释（来源）

The O(n) solution with proof by contradiction doesn't look intuitive enough to me. Before moving on, read any example of the algorithm first if you don't know it yet.

Here's another way to see what happens in a matrix representation:

Draw a matrix where the row is the first line, and the column is the second line. For example, say n=6.

In the figures below, x means we don't need to compute the volume for that case: (1) On the diagonal, the two lines are overlapped; (2) The lower left triangle area of the matrix is symmetric to the upper right area.

We start by computing the volume at (1,6), denoted by o. Now if the left line is shorter than the right line, then all the elements left to (1,6) on the first row have smaller volume, so we don't need to compute those cases (crossed by ---).

  1 2 3 4 5 6
1 x ------- o
2 x x
3 x x x 
4 x x x x
5 x x x x x
6 x x x x x x

Next we move the left line and compute (2,6). Now if the right line is shorter, all cases below (2,6) are eliminated.

  1 2 3 4 5 6
1 x ------- o
2 x x       o
3 x x x     |
4 x x x x   |
5 x x x x x |
6 x x x x x x

And no matter how this o path goes, we end up only need to find the max value on this path, which contains n-1 cases.

  1 2 3 4 5 6
1 x ------- o
2 x x - o o o
3 x x x o | |
4 x x x x | |
5 x x x x x |
6 x x x x x x

Hope this helps. I feel more comfortable seeing things this way.