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 删除。
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有