首页 > itarticle > 11. container with most water

11. container with most water

admin 11月 13, 2020 0


Leetcode
Two Points
Greedy Algorithm

题目¶

Given $n$ non-negative integers $a_1, a_2, ..., a_n$ , where each represents a point at coordinate $(i, a_i)$ . $n$ vertical lines are drawn such that the two endpoints of line $i$ is at $(i, a_i)$ 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.

分析¶

贪心算法：容器面积，取决于最短的木板

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

相关题目：

Trapping Rain Water
Largest Rectangle in Histogram,