Leetcode问题的数学解释：盛水最多的容器

Question

我正在研究中等水平的leetcode问题11。盛水的容器。除了O（n^2）的蛮力解外，还有一个复杂度为O（n）的最优解，它使用容器左右两侧的两个指针。我有点困惑，为什么这个“双指针”方法必须包含最优解。有人知道如何从数学上证明这个算法的正确性吗？这是一个我不知道的算法。非常感谢。

最初的问题是：

给定一个长度为n的整数数组高度。绘制了n条垂直线，使得第i条线的两个endpoint是（i，0）和（i，高度[i]）。找到两条与x轴一起构成容器的线，使得容器包含最多的水。返回容器可以存储的最大水量。请注意，您不能倾斜容器。

这个问题的残酷解决方案是（O（n^2））：

    def maxArea(self, height: List[int]) -> int:
        length = len(height)
        volumn = 0
        #calculate all possible combinations, and compare one by one:
        for position1 in range(0,length):
            for position2 in range (position1 + 1, length):
                if min(height[position1],height[position2])*(position2 - position1) >=volumn:
                    volumn = min(height[position1],height[position2])*(position2 - position1)
                else:
                    volumn = volumn
        return volumn

最优解方法，我写的代码是这样的（O（n））：

    def maxArea(self, height: List[int]) -> int:
        pointerOne, pointerTwo = 0, len(height)-1
        maxVolumn = 0
        #Move left or right pointer one step for whichever is smaller
        while pointerOne != pointerTwo:
            if height[pointerOne] <= height[pointerTwo]:
                maxVolumn = max(height[pointerOne]*(pointerTwo - pointerOne), maxVolumn)
                pointerOne += 1
            else:
                maxVolumn = max(height[pointerTwo]*(pointerTwo - pointerOne), maxVolumn)
                pointerTwo -= 1
        return maxVolumn

有人知道为什么这种“两指针”方法可以找到最优解吗？谢谢！

Answer 1

非正式的证明可以是这样的：假设我们在到达最佳对之前处于迭代的某个位置：

                           |
                           |
   |~~~~~~~~~~~~~~~~~~~~~~~|
   |~~~~~~~~~~~~~~~~~~~~~~~|
   |~~~~~~~~~~~~~~~~~~~~~~~|
   |~~~~~~~~~~~~~~~~~~~~~~~|
   ^                       ^
   A                       B

现在，让我们修复A（较小的垂直线），并考虑B剩下的所有选项，我们可以与之配对。很明显，所有这些容器产生的水比我们目前在a和B之间产生的水要少。

因为我们已经说过，我们还没有达到最佳解决方案，很明显，A不能成为促成它的因素之一。因此，我们移动它的指针。

Q、 E.D。

Answer 2

根据我的理解，这个想法大致是：

• 从最宽的条（即第一条和最后一条）开始，然后缩小宽度以找到可能更好的一对

步骤：

>

如果确实存在内部条形图对，则表示高度高于我们手头的条形图，因此您不应仅将指针向左或向右移动一步，而应将指针向左或向右移动到下一个更高的条形图。

为什么要向左或向右移动指针（以较小者为准）？因为较小的杆无法实现较高杆的“潜力”。

这些步骤背后的核心思想是：从内部捕获最佳解决方案的某个地方开始（步骤1），然后通过每一步，你都会找到一个比现有解决方案更好的解决方案（步骤2和3），最后你会找到最佳解决方案。

剩下一个问题供您思考：当您执行上述步骤时，是什么确保不会错过最佳解决方案？：）