You are given an array height where height[i] is the height of a vertical line drawn at position i. Pick two lines so that, together with the x-axis, they hold the most water. The water level is limited by the shorter line, and the width is the distance between the two positions. Return that maximum amount of water.
min(8, 7) * 7 = 49.- 2 <= height.length <= 10^5
- 0 <= height[i] <= 10^4
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Checking every pair of lines is O(n^2). Start with two pointers at both ends, the widest container. Its area is limited by the shorter line. Any other container using that shorter line would be narrower and still capped by the same height, so it can only be smaller. That means we can safely throw the shorter line away and move its pointer inward. Each step removes one line, giving a single O(n) pass.
Algorithm
- Set
l = 0,r = n - 1,best = 0. - While
l < r, computemin(height[l], height[r]) * (r - l)and updatebest. - Move the pointer at the shorter line inward (either one if they are equal).
- Return
best.
O(n)Space: O(1)class Solution: def maxArea(self, height: List[int]) -> int: l, r = 0, len(height) - 1 best = 0 while l < r: best = max(best, min(height[l], height[r]) * (r - l)) # The shorter line cannot do better with a narrower partner, so drop it. if height[l] < height[r]: l += 1 else: r -= 1 return best