11. Container With Most Water

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.

O(n2)方法：

class Solution(object):
    def maxArea_stupid(self, height):
        max_area = 0
        for i, vi in enumerate(height):
            for j, vj in enumerate(height):
                area = abs(i - j) * min(vi, vj)
                max_area = max(area, max_area)
        return max_area

此方法直接Time Limit Exceeded沒有通過。

O(n)方法：

class Solution(object):
    def maxArea(self, height):
        max_area = 0; i = 0; j = len(height) - 1
        while i < j:
            max_area = max(max_area, (j - i) * min(height[i], height[j]))
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return max_area

此方法AC。

思路：

①: 假設i,j為當前最大面積對應的坐標，那麼i左邊一定不會有比i更高的線，否則違背了最大面積的假設；同理j也是。

②: 所以取得更大面積的坐標一定在[i, j]的內部，從兩頭往中間靠攏，優先收縮小的。