11. Container With Most Water

Medium

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.

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.

遇到没思路的问题，先举例、画图并抽象为一个数学操作。

ai 与 aj 分别为 container 的两头，小的一边决定 container 的高度，j - i 决定 container 的宽度。

先以最简单的只考虑移动一步为标准，当小的一端向内移动时，宽度一定会变小，高度可能变小也可能变大，因此面积不确定，不能直接排除。

当大的一端向内移动时，宽度一定会变小，高度有两种情况：若移动后的边比移动前小的那条边小，高度变小；若移动后的边比移动前小的那条边大，高度不变。说明大的一端向内移动面积一定会变小 （ W' < W; H' <= H）。

因此寻找最大 container 时，所有大边向内单向移动的情况均可 不计算面积 直接跳过，只计算下一个小边内缩一位的 area 值并 compare MAX。

九章 hint：任取两个a[i]、a[j] 使得 min(a[i], a[j]) * abs(i - j)最大化 用两个指针从两侧向中间扫描，每次移动数值较小的指针

class Solution(object):
    def maxArea(self, height):
        left, right = 0, len(height) - 1
        max_area = 0
        while left < right:
            if height[left] < height[right]:
                area = height[left] * (right - left)
                left += 1
            else:
                area = height[right] * (right - left)
                right -= 1
            max_area = max(max_area, area)
        return max_area