LeetCode

Appearance

11. Container With Most Water ​

题目 ​

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

 

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: 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 2:

Input: height = [1,1]
Output: 1

 

Constraints:

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104
Related Topics
  • 贪心
  • 数组
  • 双指针

  • 👍 5488
  • 👎 0

    • 解法 ​

    py
    # leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def maxArea(self, height: List[int]) -> int:
        size = len(height)
        res = 0
        left, right = 0, size -1
        while left < right:
            width = right - left

            res = max(res, width * min(height[right], height[left]))

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1


        return res
        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度O(N)
    • 空间复杂度O(1)