[LeetCode]#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.

 

二、解析

本题意思是这样：

　　1）有一个Height<list>，里面所有元素(ai)都指的是高度。画一个XOY坐标轴，(i, ai)表示一个坐标点。连接(i, ai)和坐标轴上点(i, 0)，构成n个垂线。

　　2）两条垂线和x轴组成了一个“容器”，垂线是前后壁。容器的面积是由最短板决定的，即min(ai,aj) * (j - i)。

本题拿到后觉得思路很简单，逐条边都算一边，这样是CN2，O(n^2)的复杂度，但这种做法应该会超时。O(n)该怎么做？

根据以前的经验，O(n)是要对问题进行具体分析的。面积的决定因素有两个，一个是min(ai, aj)， 一个是(j - i)。怎样舍去那么多的不必要运算呢？因为我是要找最大的值，如果当前这个边非常小，就算把后面所有距离间隔都乘完，也是很小的，意义不大。所以我是想找到一个比较高的height，看他们的面积怎么样。

程序上来看，就是从两边开始找，存最大值。如果左边比右边低，那就保留右边，把左边向右查一个。这样的目的，是使左右两边尽可能高，这样乘积就可能更大些。

 

三、代码

class Solution:
    # @param {integer[]} height
    # @return {integer}
    def maxArea(self, height):
        i = 0
        j = len(height) - 1
        max = 0
        temp = 0
        while i < j:
            temp = min(height[i], height[j]) * (j - i)
            if temp > max:
                max = temp
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return max

 

四、总结

1、自己想完再参考别人的想法，不要急。