首先容器容纳水跟左右高度最小那一边和容器长度有关,所以我们肯定力求,左右高度和长度最大,但是在追求左右高度的过程中,容器的长度也会随之改变,因此左右高度最佳的时候可能并不是容量最多的时候,所以我们要在搜索的过程中,不断比较容量大小并保存。

但是如何进行搜索呢?因为我们要取左右两个高度中较低的哪一个作为容器的高度,所以我们有两种方法,第一种,固定一边,另一边进行遍历这样的话耗费时间是((N - 1) + ( N - 2) +...+1)

 

进而得到时间复杂度是n^{2},这时候我们想到可以用双指针来缩减时间复杂度,仅需遍历一遍数组即可时间复杂度就是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
}

Logo

码道开发者社区,聚焦华为云码道 CodeArts 代码智能体,沉淀 Agent、Skill、鸿蒙开发实战内容,供开发者查阅资料、交流技术、分享工程实践

更多推荐