leetcode-11-container-with-most-water

题目描述：

给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例：

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

分析

最朴素的方式，时间复杂度O(n^2),提交结果显示超时 :(

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        sum = 0
        l = len(height)
        for i in range(1, l):
            for j in range(i):
                tmp = (i-j) * min(height[i],height[j])
                if tmp>sum:
                    sum = tmp
        return sum

减少内部遍历层数，只遍历一遍的算法，时间复杂度只有O(n)。

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        sum = 0
        i= 0
        j = len(height) - 1
        while i<j:
            h = 0
            b = j - 1
            if height[i] < height[j]:
                h = height[i]
                i += 1
            else:
                h = height[j]
                j -= 1
            tmp = b * h
            if tmp > sum:
                sum = tmp
        return sum