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

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

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

leetcode_question_11


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

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

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

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

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

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

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


下面是我参考题解写的。真的很难想到,这题能用复杂度为 O(n) 的方法解决。

添加一条评论

电子邮件地址不会被公开。 必填项已用*标注