仰望星空，脚踏实地

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

发表于 更新于 分类于 Valine：

翻译一篇双指针法的证明，来自 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);
	}
}