11. Container With Most Water
by Aaron • 3/9/2025, 8:51:42 AM
Description
Medium
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.
Solution
找到兩個 vertical lines，使得他們和 x-axis 組成的 container 能夠存放最多的水。這個問題可以用 two pointer 的方式來解決。我們可以用兩個 pointer 分別指向 array 的頭和尾，然後計算這兩個 pointer 之間的面積，並且更新最大的面積。接著我們可以移動較短的那一邊，因為如果我們移動較長的那一邊，面積只會變小。這樣我們就可以在 O(n) 的時間複雜度內解決這個問題。
- ruby
# @param {Integer[]} height
# @return {Integer}
def max_area(height)
area = -1
left = 0
right = height.size - 1
while left < right
left_height = height[left]
right_height = height[right]
current_area = [left_height, right_height].min * (right - left)
if current_area > area
area = current_area
end
if left_height > right_height
right -= 1
else
left += 1
end
end
area
end
- golang
func maxArea(height []int) int {
area := -1
left := 0
right := len(height) - 1
for left < right {
currentArea := min(height[left], height[right]) * (right - left)
area = max(area, currentArea)
if height[left] > height[right] {
right -= 1
} else {
left += 1
}
}
return area
}
func max(a int, b int) int {
if( a > b) {
return a
}
return b
}
func min(a int, b int) int {
if(a < b) {
return a
}
return b
}