给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
img
示例:
输入: [1,8,6,2,5,4,8,3,7] 输出: 49
解答
怎么感觉就只能硬算
看了题解发现还能双指针
思路就是，头尾两个指针，计算一下面积。移动其中高度小的那一个。
因为移动高的那个，面积必然减小，移动小的，有可能变大。
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height)-1
ans = 0
while left < right:
temp = (right - left)*min(height[left], height[right])
if temp > ans:
ans = temp
if height[left] > height[right]:
right -= 1
else:
left += 1
return ans
Runtime: 168 ms, faster than 7.64% of Python3 online submissions for Container With Most Water.
Memory Usage: 15.3 MB, less than 5.26% of Python3 online submissions for Container With Most Water.
func min(a, b int) int {
if a < b {
return a
}
return b
}
func maxArea(height []int) int {
var left, ans int
right := len(height) - 1
for left < right {
temp := (right - left) * min(height[left], height[right])
if temp > ans {
ans = temp
}
if height[left] > height[right] {
right--
} else {
left++
}
}
return ans
}
Runtime: 12 ms, faster than 90.29% of Go online submissions for Container With Most Water.
Memory Usage: 5.6 MB, less than 46.67% of Go online submissions for Container With Most Water.
var maxArea = function(height) {
let left = 0,
right = height.length - 1,
ans = 0
while (left < right) {
const temp = (right - left) * Math.min(height[left], height[right])
if (temp > ans) {
ans = temp
}
if (height[left] > height[right]) {
right--
} else {
left++
}
}
return ans
};
Runtime: 56 ms, faster than 87.22% of JavaScript online submissions for Container With Most Water.
Memory Usage: 35.4 MB, less than 90.91% of JavaScript online submissions for Container With Most Water.
另一种做法是直接在while里面判断
var maxArea = function(height) {
let left = 0,
right = height.length - 1,
ans = 0
while (left < right) {
if (height[left] > height[right]) {
let temp = height[right] * (right - left)
ans = Math.max(temp, ans)
right--
} else {
let temp = height[left] * (right - left)
ans = Math.max(temp, ans)
left++
}
}
return ans
};
Runtime: 60 ms, faster than 70.80% of JavaScript online submissions for Container With Most Water.
Memory Usage: 35.7 MB, less than 42.42% of JavaScript online submissions for Container With Most Water.
反而变慢了。。
class Solution:
def maxArea(self, height: List[int]) -> int:
left = 0
right = len(height)-1
ans = 0
while left < right:
if height[left] > height[right]:
temp = (right - left)*height[right]
right -= 1
else:
temp = (right - left)*height[left]
left += 1
ans = max(temp, ans)
return ans
Runtime: 148 ms, faster than 54.05% of Python3 online submissions for Container With Most Water.
Memory Usage: 15.6 MB, less than 5.26% of Python3 online submissions for Container With Most Water.
