11. 盛最多水的容器（中等）

• 难度: 中等
• 考察: 数组
• 来源: https://leetcode-cn.com/problems/container-with-most-water/description/
• 题解: https://github.com/azl397985856/leetcode/blob/master/problems/11.container-with-most-water.md
• 题解: https://github.com/MisterBooo/LeetCodeAnimation/blob/master/0011-maxArea/Article/0011-maxArea.md

题目

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:

输入：[1,8,6,2,5,4,8,3,7]
输出：49

思路

暴力法

容器可以容纳水的容量=两条垂直线中最短的那条*两条线之间的距离 现在的情况是，有很多条线，让你计算两两之间能装的最多的水，其实暴力法之间就能解决这个问题，但是它的时间复杂度也达到了O(n^2)

双指针法

思路：使用两个指针（resource和last）分别指向数组的第一个元素和最后一个元素，然后我们计算这两条“线”之间能容纳的水的容量，并更新最大容量（初始值为0）；接着我们需要将指向元素值小的那个指针前移一步，然后重复上面的步骤，直到resource = last循环截止。

关键点

• 木桶原理，容量取决于短的木板

复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(N)

代码

暴力法

func maxArea(height []int) int {
	var max int
	for i := 0; i < len(height)-1; i++ {
		for j := i + 1; j < len(height); j++ {

			var area int
			if height[i] >= height[j] {
				area = height[j] * (j - i)
			} else {
				area = height[i] * (j - i)
			}
			if area > max {
				max = area
			}
		}
	}
	return max
}

双指针法

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