0011._container_with_most_water.md

11. Container With Most Water

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/container-with-most-water/description/

内容描述

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.

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.

 

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******

由于ai和aj (i<j) 组成的container的面积：S(i,j) = min(ai, aj) * (j-i)

当height[left] < height[right]时，对任何left < j < right来说

1. min(height[left], height[j]) <= height[left] = min(height[left], height[right])
2. j - left < right - left

所以S(left, right) = min(height[left], height[right]) * (right-left) > S(left, j) = min(height[left], height[j]) * (j-left)

这就排除了所有以left为左边界的组合，因此需要右移left。

因此：

• height[left] < height[right]，需要右移left.

• 同理，当height[left] > height[right]时，需要左移right。

• 而当height[left] = height[right]时，需要同时移动left和right。

思路整理： left = 0, right = n-1

1. height[left] < height[right], left++
2. height[left] > height[right], right--
3. height[left] = height[right], left++, right--

终止条件：left > right

这个证明大快人心

beats 82.89%

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