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 and n is at least 2.

思路：
这个题还是比较容易实现的，主要就是题目理解起来比较绕（英语水平有限）。大概就是在二维坐标系中，(i, ai) 表示 从 (i, 0) 到 (i, ai) 的一条线段，给定了一个数组[a1…..an]，这就有了n条线段。任意两条这样的线段和 x 轴组成一个木桶，找出能够盛水最多的木桶，返回其容积。

  1. 高选较短的，而最长的一种情况显然就是n-1，但是这不能保证面积是最大的。
  2. 这个时候谁短谁向中间移，这个时候更新一下面积即可，移动的时候可以借助两个变量当做指针。短的向中间移，即我们说的贪婪算法，选取局部最优。
  3. 当指针相等的时候结束遍历。算法时间复杂度为O(n)。

实现：

1
2
3
4
5
6
7
8
9
def maxArea(height):
        left, right, max_area = 0, len(height)-1, 0
        while left < right:
            max_area = max(max_area,min(height[right],height[left])*(right-left))
            if height[left] <= height[right]:
                left += 1
            elif height[left] > height[right]:
                right -= 1
        return max_area