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