盛最多水的容器。给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
双指针。左指针最左,符合条件时右移;右指针最右,符合条件时左移。左指针和右指针,谁小谁移动;同样大,移动左指针。时间复杂度O(N),额外空间复杂度O(1)。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
arr := []int{1, 8, 6, 2, 5, 4, 8, 3, 7}
ret := maxArea2(arr)
fmt.Println(ret)
}
func maxArea2(h []int) int {
max := 0
l := 0
r := len(h) - 1
for l < r {
max = getMax(max, getMin(h[l], h[r])*(r-l))
if h[l] > h[r] {
r--
} else {
l++
}
}
return max
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
执行结果如下: