Rearch Interest: Visualization">
11. 盛最多水的容器
题目描述
给你n个非负整数 \(a_1\), \(a_2\), ..., \(a_n\)，每个数代表坐标中的一个点 \((i, a_i)\)。
在坐标内画n条垂直线，垂直线i的两个端点分别为
\((i, a_i)\) 和 \((i, 0)\)。
找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
你不可以倾斜容器。
示例1：
输入：
height = [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 * 104 -
0 <= height[i] <= 3 * 104
我的代码 (Timeout)
思路：试图基于“一次遍历”的想法来做，也就是随着每次新读入一个bar就去检查一次最优解； 但是面积由高(maxHeight)×宽(i-j)共同决定， 而每次新读入的这个bar的宽都会增加1 (因为i后移了)， 所以每次都得去找离最新读入的bar最远又最高的那个。不太好确定。
\(T(N) = O(N)\), \(S(Height) = O(Height)\)
{.line-numbers} 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
class MySolution11
{
public int maxArea(int[] height)
{
if (height.length<=1) return 0;
int maxHeight = height[0]; int maxIndex = 0;
int maxVal = -1;
for (int i=1; i<height.length; i++)
{
int newHeight = height[i];
if (newHeight>maxHeight)
{
maxHeight = newHeight;
maxIndex = i;
}
for (int j=0; j<i&&j<=maxIndex; j++)
{
int minH = height[j]<newHeight?height[j]:newHeight;
int w = i - j;
maxVal = maxVal<(minH*w)?(minH*w):maxVal;
}
}
return maxVal;
}
}
1 | class MySolution11 |
方法：双指针
\(T(N) = O(N)\), \(S(N) = O(1)\)
首先将双指针分别指向数组的头和尾。得到一个初始的容水量。 然后每次都移动一个指针——移动height较小的那个指针，试图得到一个更大的容水量。 直到两个指针重叠。
证明: > 双指针代表了什么？
双指针 代表的是可以作为容器边界的所有位置的范围。 一开始双指针指向一头一尾，表示数组中的所有位置都可以作为容器的边界。 在这之后，我们每将小指针移动一个位置，就代表我们认为这个指针不可能再作为容器的边界了。
为什么移动小指针？——定量证明
假设一开始左右指针指向的数字分别是 \(x\) 和 \(y\), 然后我们假设 \(x ≤ y\). 同时，两指针之间的距离为 \(t\).则此时容器的容量为: \[min(x,y)*t = x*t\] 此时我们可以断定，如果我们保持左指针不变，则无论右指针移动到哪里 (注意这里右指针只能往左移动——因为我们还处在第一步，两个指针都还在边界处)，容水量都不会超过 \(x*t\) 了: 假设我们左移右指针，此时指向的数是 \(y_1\)、两指针之间的距离是 \(t_1\). 则显然有 \(t_1 < t\), 且 \(min(x, y_1) ≤ min(x, y)\): - 若 \(y_1≤y\) 则 \(min(x,y_1) ≤ min(x,y)\); - 若 \(y_1<y\) 则 \(min(x,y_1) = x = min(x,y)\);
因此有: \[min(x,y_t) * t_t < min(x,y) * t\] 即，无论我们怎么移动右指针，得到的容量都小于移动前的容量。 此时，我们应该舍弃这个旧的左指针 (小指针) ，然后将左指针右移一个位置，才有可能会作为新的边界。
通过这种做法，我们将问题的规模减小了1，得到了一个新的、规模减小了的数组的左右边界。 因此，我们可以继续像考虑第一步的时候一样考虑这个问题: - 求出当前双指针对应的容器容量； - 因为小指针今后不能再作为边界了，所以将其丢弃并移动到新的位置。
1 | class Solution11 |