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 and n is at least 2.
11. Container With Most Water
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49

题意： 给出一个数组，数组中的每一个数相当于一块板子，两块板子这两个数对应index的距离形成一个桶，痛的容积由最短板的长度（数的大小）以及index的距离的乘积决定，要求求出这个数组最大的容积。
方法一： 暴力解法，计算出所有可能的容积，保留最大的即可，此方法时间复杂度为 $O(n^2)$ 超时。
代码1：

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

方法二： 双指针法，两个指针i， j定位到数组的头部和尾部，若指针i对应的值比指针j要小，那么此时以i为一块木板，容积最大的另一块木板必定为j，因为此时i为短板，容积是由短板和Index距离所决定的，算出此时的容积并将指针i往右移，（指针j左移肯定是不会使得容积增大的，而i右移则有可能使得容积增大）继续进行判断，若指针i对应的值比指针j要大，那么j就是短板，容积由j决定，算出此时的容积，并将指针j左移。直到最后i和j相遇停止，返回最大容积。时间复杂度为 $O(n)$ 。
　　有人可能会质疑，若在某次的迭代过程中，i对应的值小于j对应的值，此时应该将指针i右移，那么是否存在k，有k>j，且i和k形成的容积是最大容积？这种情况是不可能发生的，因为我们的指针j之所以会由k位置移动到目前的j位置，必然存在位置m，且m <i，有m位置对应的值大于k位置对应的值（此时才会左移），那么由m, k形成的容积必然大于i，k形成的容积，因此i，k不会形成最大容积。
代码2：

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        n = len(height)
        i = 0
        j = n -1
        maxcontain = 0
        while i!= j:
            if height[i] >= height[j]:
                contain = height[j] * (j - i)
                j -= 1
            else:
                contain = height[i] * (j - i)
                i += 1
            if contain > maxcontain:
                maxcontain = contain
        return maxcontain

11. Container With Most Water

题目：

相关推荐