题目 #

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

思路1 #

分析 #

自己想的动态规划

定义两个函数

$f(n)$ 代表前 $n$ 个数组中最大的容量
$g(n)$ 代表以 $n$ 结尾的最大的容量

那么有

$$ f(n+1) = max(f(n), g(n+1)) $$

然后，时间复杂度超了。。。。应该是很多计算没必要

思路2 #

分析 #

$i$ 和 $j$ 之间的容量表示为

$$ container(i, j) = (j - i) \times min(height[i], height[j]) $$

那么先要求 $j-i$ 最大，也就是两个边界

向内收缩的时候，$j-i$ 会减小，需要找到一个比小的边界更高的才行，不然无法计算出比结果更大的

那么就需要较小的边界收缩，较大的不动

代码实现 #

 1func maxArea(height []int) (result int) {
 2	left, right := 0, len(height)-1
 3
 4	for right > left {
 5		minValue := height[left]
 6		if minValue > height[right] {
 7			minValue = height[right]
 8		}
 9
10		tmp := (right - left) * minValue
11		if tmp > result {
12			result = tmp
13		}
14
15		// less border move, move to a bigger border than minValue
16		if height[left] < height[right] {
17			for right > left && height[left] <= minValue {
18				left++
19			}
20		} else {
21			for right > left && height[right] <= minValue {
22				right--
23			}
24		}
25	}
26	return
27}

思路3 #

官方解答

分析 #

和思路2差不多，还更差一点，但是代码量小了

通俗来讲，小的移动，虽然可能变得更差，但是总比不动（或者减小）强

代码实现 #

 1func maxArea1(height []int) (result int) {
 2	left, right := 0, len(height)-1
 3
 4	for right > left {
 5		minValue := height[left]
 6		if minValue > height[right] {
 7			minValue = height[right]
 8		}
 9		tmp := (right - left) * minValue
10		if result < tmp {
11			result = tmp
12		}
13		if height[left] < height[right] {
14			left++
15		} else {
16			right--
17		}
18	}
19	return
20}