【LeetCode每日一题】11.盛最多水的容器.md

发表于   |   分类于 ，   |   阅读次数

LeetCode 11.盛最多水的容器

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为(i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
示例 3：
输入：height = [4,3,2,1,4]
输出：16
示例 4：
输入：height = [1,2,1]
输出：2
提示：

  • n = height.length
  • 2 <= n <= 3 * 10^4
  • 0 <= height[i] <= 3 * 10^4

这个题目要求计算能够盛放的最多的水，这里其实是求的面积。

我们知道面积公式为： 面积=长*高

而在该题目中，长度和高度都是变量，所以，最直观，最简单的想法是，将长度和高度作为两个变量，穷举出所有可能的容器，计算所有容器能够盛的水，取其最大的即可。
这样的话，我们就需要双层循环遍历，时间复杂度为 O(n^2)。这个题目被设计成中等难度，显然这个穷举法不是题目要考察的。

我们该怎么把这由于两个变量导致的两层循环给优化一下呢？

如果我们能定住其中一个变量，或者将另外一个变量的变化引起的作用，不能实质改变问题的求解，让问题的解只和其中一个变量发生作用，就可以减掉一层循环，将复杂度降到O(n)。

由于面积=长度*高度，而在本题中，长度和高度，都不是固定的，所以上面说的定住一个变量，恐怕难以实现。

那我们能不能改变一下思路，让其中一个变量“失去”作用，最终的最大盛水量只和其中一个变量有关呢？

面积=长度*高度。其中高度就是给的一个数组，其中每个元素都是一个高度，而长度就是两个高度之间的距离。

如果我们将长度不断缩小，那么要求最大面积，最大面积就只和高度相关了，因为长度不断缩小，要想面积增大，那么只能是高度不断增大。

我们取长度最大的两个高度作为容器的边界，即height[0]和height[length-1]，然后不断缩小长度。
那缩小长度时，怎么确定是移动左边界还是右边界呢？依据就是上面说的，由于长度缩小，要想面积增大，那只能是高度增加，我们应该移动左右边界中，小的那一个边界，这样才有可能遇到更大的边界，面积才有可能变大。

其操作过程如下：

取height[0]和height[8]为左右边界，这时面积为8.


由于height[0]<height[8]，因此移动左边界，这时面积为7*7=49.
根据此逻辑，不断移动左右边界，计算出相应的面积，选取最大面积即可。





这样我们只需要O(n)复杂度即可完成实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func maxArea(height []int) int {
	length := len(height)
	start, end := 0, length-1
	maxArea := 0
	for start < end {
		area := (end - start) * min(height[start], height[end])
		maxArea = max(area, maxArea)
		if height[start] < height[end] {
			start++
		} else {
			end--
		}
	}
	return maxArea
}