11. Container With Most Water
- Total Accepted: 99353
- Total Submissions: 277586
- Difficulty: Medium
- Contributors: Admin
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.
Code
class Solution(object): def maxArea(self, height): """ :type height: List[int] :rtype: int """ lp, rp = 0, len(height)-1 max_area = 0 while lp < rp: max_area = max(max_area, min(height[lp],height[rp]) * (rp-lp)) if height[lp] < height[rp]: lp += 1 else: rp -= 1 return max_area
Idea
The time complexity is O(N). The idea is that if height[lp] < height[rp]
, then the bottleneck to determine the container volume is height[lp]
. That means the container formed by height[lp]
and height[rp']
for any rp'
< rp
must have smaller volume than that formed by height[lp]
and height[rp]
. In this case, lp
should move to right.
You can easily deduct the other case: height[rp] < height[lp]
.
Reference: https://discuss.leetcode.com/topic/3462/yet-another-way-to-see-what-happens-in-the-o-n-algorithm