这道题以前做过，但是忘记怎么做的了。第一次交了一个双重循环的暴力。查看题解一下就明白了正确的贪心算法。
题目描述
给你 N 个非负的正整数 a1,a2,a3,…an，每个代表了坐标轴上的一个点(i，ai)。n 条垂直的线连接点和 x 轴，要求找出两条线，让它们和 x 轴组成的容器的容积最大。
解题思路
正解是用两点逼近的算法。首先容器的高度是由最短的那条线决定的。
维护一个变量记录最大容积。记录所取的两端的端点位置，每次计算当前情况的容积，并更新最大容积。之后更新较短的那条线的端点位置(一定是更新较短的端点位置，否则容积一定小于当前容积，因为只有宽度减小)，更新方法为向另一端的方向遍历直到遇到一条比当前线高度高的线（比当前线高度低的线组成的容积一定小于当前情况的容积）。
以下是代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| func maxArea(height []int) int {
left, right := 0, len(height)-1
res := 0
for left < right {
minHeight := 0
if height[left] < height[right] {
minHeight = height[left]
} else {
minHeight = height[right]
}
newArea := (right - left) * minHeight
if newArea > res {
res = newArea
}
if height[left] < height[right] {
newLeft := left + 1
for newLeft < right && height[newLeft] < height[left] {
newLeft = newLeft + 1
}
left = newLeft
} else {
newRight := right - 1
for newRight > left && height[newRight] < height[right] {
newRight = newRight - 1
}
right = newRight
}
}
return res
}
|