LeetCode-盛最多水的容器-11题

题目中要求计算最大面积，即需要选择对应的长和宽。

最终解决方法：使用对撞指针

对撞指针的概念：是指在数组的两个端引入两个指针，左指针不断向右移动，右指针不断向左移动。最终到达两个指针相遇的时候，将所有可能遍历完成。因此其时间复杂度可以理解为O(n)

思路：

首先设置两个指针start和end，使其分别从数组的两端向中间移动

每次移动之前的条件是：已经通过比较选择出当前start和end位置上最小的值，作为现在面积计算中的高（high）。

并且需要根据两个位置上值的大小，选择移动哪个指针

这里，我们考虑了题目要求：求最大的面积，因此需要将现在较小的值对应的指针进行移动，以寻找更大的高度high

具体代码如下：

func maxArea(height []int) int {max := 0//对撞指针的解法start,end := 0,len(height)-1 //定义两个指针，分别指向数组的两端for start<end{//循环high := 0 //每次初始值为0wid := end-start //保存当前的宽度if height[start]<height[end]{//说明左边的太小了，需要尝试移动左指针，以寻找更大的。因为“木桶效应”high = height[start]start++ //左边太小了，需要换个更大的试试}else{high = height[end]end--}if max<high*wid{max = high*wid}}return max
}

上述代码中，我们使用for循环，在每次比较中，我们选择两者中更小的值作为high，并将其对应的指针进行继续移动

下面我们对上述过程进行了优化

实际在上述过程中，我们完全可以先计算出当前的面积（使用两端最小的值作为高），再进行指针的移动

func maxArea(height []int) int {//对撞指针的解法start,end := 0,len(height)-1 //定义两个指针，分别指向数组的两端n := len(height)-1max := min(height[start],height[end])*(end-start)for start<end{//循环temp := min(height[start],height[end])*(end-start)if max<temp{max = temp}if height[start]<height[end]{//说明左边的太小了，需要尝试移动左指针，以寻找更大的。因为“木桶效应”start++ //左边太小了，需要换个更大的试试}else{end--}}return max
}
func min(a,b int)int{if a>b{return b}return a

起初的思路

是想通过设置两个for循环，通过遍历计算每一种可能的情况，并与最大的max进行比较，从而得到最大的面积。

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

但其实执行过后能够发现，超时。因为进行了一些不必要的计算