盛最多水的容器

题目

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/container-with-most-water

给定 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
1
2

双指针法

思路:先将指针指向两端的直线,再选择向内移动短的那端的指针。因为若移动长的那端,那么得到的新的容量一定被当前容量小。反之移动短的那段,可能出现更大的容量。过程如下:

  • 使用 hi, hj 表示两个直线的高度,初始化的值:i=0, j=n-1
  • 面积的计算公式为:s(i, j) = min(hi, hj) * (j - i)
  • 向内移动指针会导致底边缩减 1 个单位,不论是 i 还是 j。就是和当前比应该是 (j-i)-1。
  • 若向内移动长边指针,那么 min(hi, hj) 不会变大,甚至会变小,同时 底边一定缩减,因此 S(i, j) 一定变小。
  • 若想内移动短边指针,那么 min(hi, hj) 可能会变大。因此可能会得到最大的面积

因此我们可假定初始化状态为最大面积,然后逐渐移动短边,若获得更大的面积,更新它!

盗一张图来自 Leetcode 用户 krahets:( https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/ ):

Go 编码实现

LeetCode 下:

执行结果:通过

执行用时 :12 ms, 在所有 golang 提交中击败了97.78%的用户

内存消耗 :5.6 MB, 在所有 golang 提交中击败了65.79%的用户

func maxArea(height []int) int {
	// 初始化为左右两端
	left, right := 0, len(height) - 1
	// 当前最大面积
	s := 0
	// 新面积
	ns := 0
	// left 和 right 未相交,执行循环
	for left < right {
		// 确定短边,移动和确定是否为最大面积
		// 若为最大面积,记录下来
		if height[left] < height[right] {
			ns = height[left] * (right - left)
			if s < ns {
				s = ns
			}
			left ++
		} else {
			ns = height[right] * (right - left)
			if s < ns {
				s = ns
			}
			right --
		}
	}
	return  s
}
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