LeetCode 11 Container With Most Water

Posted on | In | 阅读

2-SUM 同类型题目

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.

img

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

  • 算法：

    刚开始设置最左边和最右边两个板，记录当前面积，然后把短的那边的指针向中心移动一个位置，比较面积，以此类推；

  • 证明：

    以左边指针为例，如果左边较短，那么右边的指针无论怎么向左移动都不可能得到更大的面积了，所以可以看作直接跳过大层循环，即左边指针向右一位。右边指针同理；

    左边向右一位后，右边的指针不需要回到最右边，因为右边指针的右边不可能有比左边指针移动前更大的（相当于双方打擂台，守擂的一定比对方之前打擂失败的都要强），所以左指针移动后不可能通过右指针右边的数得到更好的答案。

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        mx = 0
        i = 0
        j = len(height) - 1
        while i < j:
            v = min(height[i], height[j]) * (j-i)
            mx = max(mx, v)
            if height[i] < height[j]:
                i += 1
            else:
                j -= 1
        return mx