Leetcode 11:盛最多水的容器 双指针法的证明

翻译一篇双指针法的证明,来自 Leetcode 主站 kongweihan 的评论

原问题按此:盛最多水的容器 - 力扣(LeetCode)

leetcode_question_11

这是用矩阵来表示的另一种方法:

画一个矩阵,它的行表示第一条线段,列表示第二条线段。用 n=6 的情况做个例子。

在下图中,x 表示我们不需要计算的面积,因为:(1)对角线上的值,代表两条线重叠了;(2)矩阵左下角三角形区域和右上角是对称的。

我们从 (1,6) 开始来计算面积,用 o 来表示。现在,如果左边的线段比右边的短,那么在第一行的除 (1,6) 外的所有元素的面积都小于(等于)它。所以对于这些情况我们就不需要计算它们的值了(用 --- 划掉 )。

1
2
3
4
5
6
7
  1 2 3 4 5 6
1 x ------- o
2 x x
3 x x x
4 x x x x
5 x x x x x
6 x x x x x x

然后我们移动左边的线段,计算 (2,6)。现在,如果右边的线段短一些,所有低于 (2,6) 的情况都可以排除了。

1
2
3
4
5
6
7
  1 2 3 4 5 6
1 x ------- o
2 x x o
3 x x x |
4 x x x x |
5 x x x x x |
6 x x x x x x

无论这条 o 的路径是怎样的,我们最终只要找到这条路径上最大的数值就可以了,而这需要 n-1 步计算。

1
2
3
4
5
6
7
  1 2 3 4 5 6
1 x ------- o
2 x x - o o o
3 x x x o | |
4 x x x x | |
5 x x x x x |
6 x x x x x x

希望对你有所帮助。用这种方式来看我觉得舒服多了。


下面是我参考题解写的。真的很难想到,这题能用复杂度为 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
// Q010.java

class Solution10 {
public int maxArea(int[] height) {
int l = 0;
int r = height.length-1;
int max = 0;

while(l<r) {
max = Math.max(max, Math.min(height[l], height[r])*(r-l));
if (height[l]<height[r]) l++;
else r--;
}

return max;
}
}

public class Q010 {
public static void main(String[] args) {
Solution10 s = new Solution10();
int[] a = {1,8,6,2,5,4,8,3,7};
int m = s.maxArea(a);
System.out.println(m);
}
}