Leetcode题目数学解释：Container With Most Water

Question

我正在研究一个中等级别的 leetcode 问题 11. Container With Most Water。除了 O(n^2) 的蛮力解决方案外，还有一个复杂度为 O(n) 的最优解决方案，通过使用来自容器左右两侧的两个指针。我有点困惑为什么这种“双指针”方法必须包括最优解。有谁知道如何从数学上证明这个算法的正确性？这是我不知道的算法。谢谢！

原题是：

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container.

这个问题的一个残酷的解决方案是(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

根据我的理解大概思路是：

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

步骤：

我们需要有能力遍历所有 'potential' 候选人（候选人比我们手头的候选人更好，而不是像你在残酷的解决方案中所做的那样从所有候选人开始）因此从外部开始bars 并且不会遗漏任何内部对。
如果确实存在内部柱对，则表示高度高于我们手头的柱，因此您不应该只是#Move left or right pointer one step，而是#Move left or right pointer to next taller bar 。
为什么#Move left or right pointer whichever is smaller？因为较小的条不符合较高条的 'potential'。

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

留给你一个思考的问题：是什么保证你在执行上述步骤时不会遗漏最优解？ :)

Answer 2

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


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

现在让我们修正 A（较小的垂直线）并考虑所有 B 左边的选项，我们可以与之配对。很明显，所有这些都产生了一个比我们目前在 A 和 B 之间更小的水量的容器。

既然我们已经声明我们还没有达到最佳解决方案，显然 A 不能成为促成它的线路之一。因此，我们移动它的指针。

Q.E.D.

Leetcode题目数学解释：Container With Most Water

Mathematical explanation of Leetcode question: Container With Most Water

python

arrays

algorithm