leetcode100 盛最多水的容器 go语言
·
首先容器容纳水跟左右高度最小那一边和容器长度有关,所以我们肯定力求,左右高度和长度最大,但是在追求左右高度的过程中,容器的长度也会随之改变,因此左右高度最佳的时候可能并不是容量最多的时候,所以我们要在搜索的过程中,不断比较容量大小并保存。
但是如何进行搜索呢?因为我们要取左右两个高度中较低的哪一个作为容器的高度,所以我们有两种方法,第一种,固定一边,另一边进行遍历这样的话耗费时间是((N - 1) + ( N - 2) +...+1)
进而得到时间复杂度是,这时候我们想到可以用双指针来缩减时间复杂度,仅需遍历一遍数组即可时间复杂度就是N。原因就是:我们分别设置0 和 len(height) 作为左右指针,只需将相对较小的一个高度移动,因为容器的高度由相对较小的一边决定,左右相同时移动任意一边都可以,并且在移动中不断更新容器的最大容量,当他们两个相遇已经遍历出最优结果。
具体代码实现,欢迎讨论
func maxArea(height []int) int {
l := len(height)
left := 0
right := l - 1
ret := min(height[left], height[right]) * (l - 1)
for left < right{
if height[left] <= height[right] {
left ++
}else{
right --
}
ret = max(ret, min(height[left], height[right]) * (right - left))
}
return ret
}
更多推荐



所有评论(0)