跳转至

11. Container With Most Water

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,

参考视频