LeetCode 11 [Container With Most

原题

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

样例
给出[1,3,2], 最大的储水面积是2.

解题思路

• 根据题意，怎么求解容纳水的面积呢？假设有两个点i和j，面积 = min(a[i], a[j]) * (j - i)
• 首先，维护一个全局变量 - Area
• 所以每次要移动左右两个高度中较小的那一个，才有可能让面积增大。因为当你移动了较大的那一条边之后，再求两条边的最小值，还是不会超过移动之前的最小值，甚至还有可能会减小
• Two Pointers - 对撞型指针

完整代码

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        res = 0
        if not height or len(height) < 2:
            return res
            
        left, right = 0, len(height) - 1
        res = min(height[left], height[right]) * (right - left)
        while left < right:
            if height[left] < height[right]:
                res = max(res, height[left] * (right - left))
                left += 1
            else:
                res = max(res, height[right] * (right - left))
                right -= 1
        return res