11.M 盛最多水的容器

Problem: 11. 盛最多水的容器

思路

最简单的思路是两层循环，分别计算任意两个边界形成的容量，但是时间复杂度为O($N^2$)

优化后的思路为双指针。

left指向左边界，right指向右边界，每次比较左右边界哪边的高度更低，左边界更低，则左边界右移；否则，右边界左移。这么移动的原因是，只有移动更低的边界，才有可能获得更大的容量。

每次移动后的容量等于左右边界的最小值乘以左右边界下标之差。

Code

func maxArea(height []int) int {
	left, right := 0, len(height)-1
	maxArea := 0
	for left <= right {
		area := min(height[left], height[right]) * (right - left)
		maxArea = max(maxArea, area)
		if height[left] < height[right] {
			left++
		} else {
			right--
		}
	}

	return maxArea
}

func min(a, b int) int {
	if a < b {
		return a
	}

	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}