关于leetcode个人解题总结:双指针的妙用leetcode11盛最多水的容器

47次阅读

共计 1027 个字符，预计需要花费 3 分钟才能阅读完成。

题目形容如下

要找到最大容量
首先确定公式
area=（右左标点 - 左坐标点）*min（height[左],height[右]）

首先能想到的当然是简略粗犷的暴力解法

func maxArea(height []int) int {
    max:=0
    for i:=1;i<len(height);i++{
        for j:=0;j<i;j++{area:=(i-j)*minNum(height[i],height[j])
            max=maxNum(max,area)
        }
    }
    return max
}
func minNum(a int,b int)int{if(a<b){return a}
    return b
}
func maxNum(a int,b int)int{if(a>b){return a}
    return b
}

让咱们看看提交后果

尽管通过了样例，但在提交时因为超出事件限度，不予通过
显然，这道中等难度的题不容许咱们用 O（n^2）这样辣鸡的算法来解决

要将其优化，我思考过动静布局，分治法，然而显然实现难度都较大
而，双指针，这个神奇的工具，
再一次展现出了他神奇的魅力

上代码

func maxArea(height []int) int {
    max:=0
    left,right:=0,len(height)-1
    for left<right{area:=(right-left)*minNum(height[left],height[right])
        max=maxNum(max,area)
        if height[left]<height[right]{left++}else {right--}
    }
    return max
}
func minNum(a int,b int)int{if(a<b){return a}
    return b
}
func maxNum(a int,b int)int{if(a>b){return a}
    return b
}

首先，先将初始状态设置为容器底部最大的状态，同时双指针开始挪动，底部逐步放大，寻找最大容积

对于边界的挪动，每次抉择一边木板向内挪动，两边的木板按高度分为长板和短板

若向内挪动短板，水槽的短板可能变大，因而下个水槽的面积可能增大。
若向内挪动长板，水槽的短板不变或变小，因而下个水槽的面积肯定变小。

因而，数字较小的这一边不可能再成为边界，能够间接将其排除

每次挪动边界一次，便将问题的规模放大了 1，这样直到两个指针重合，咱们就把所有的状况思考了一遍，全局变量 max 便是最终的后果

这里只挪动了指针 n 次，算法的复杂度降到了 O（n），通过提交便是轻而易举

正文完