2021-05-24：盛最多水的容器。给你 n 个非负整数 a1，a2，...，an
原创2021-05-24：盛最多水的容器。给你 n 个非负整数 a1，a2，...，an
原创
福大大架构师每日一题
修改于 2021-05-25 10:36:37
修改于 2021-05-25 10:36:37
2021-05-24：盛最多水的容器。给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
福大大 答案2021-05-24：
双指针。左指针最左，符合条件时右移；右指针最右，符合条件时左移。左指针和右指针，谁小谁移动；同样大，移动左指针。时间复杂度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
}
}执行结果如下：
图片
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读