我正在做一個中等級別的 leetcode 問題11. Container With Most Water。除了 O(n^2) 的蠻力解決方案外，通過使用容器左右兩側的兩個指標，還有一個復雜度為 O(n) 的最優解決方案。我有點困惑，為什么這種“雙指標”方法必須包含最優解。有誰知道如何在數學上證明這個演算法的正確性？這是一個我不知道的演算法。謝謝！
原來的問題是：
給定一個長度為 n 的整數陣列高度。繪制了 n 條垂直線，使得第 i 條線的兩個端點是 (i, 0) 和 (i, height[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
有誰知道為什么這種“雙指標”方法可以找到最優解？謝謝！
uj5u.com熱心網友回復：
根據我的理解，這個想法大致是：
- 從最寬的柱（即第一個和最后一個柱）開始，然后縮小寬度以找到可能更好的對。
腳步：
我們需要有能力遍歷所有“潛在”候選人（這些候選人比我們手頭的更好，而不是像你在殘酷的解決方案中所做的所有候選人），因此從外部酒吧開始，不會錯過任何內部配對。
如果確實存在內部條形對，則意味著高度高于我們手頭上的條形，因此您不應該只是
#Move left or right pointer one stepbut#Move left or right pointer to next taller bar。為什么
#Move left or right pointer whichever is smaller？因為較小的條不能滿足較高條的“潛力”。
這些步驟背后的核心思想是：從內部捕獲最佳解決方案的某個地方開始（第 1 步），然后通過每一步，您將獲得比您現有的更好的解決方案（第 2 步和第 3 步），最后您將到達到最優解。
留給您思考的一個問題是：在執行上述步驟時，如何確保不會錯過最佳解決方案？:)
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/469105.html