來源：Container With Most Water - LeetCode
【leetcode】Container With Most Water 講解
問題：
如標題，這篇文章是要講解 leetcode 的演算法題目。講解的原因在於我認為 Container With Most Water 是一個很不錯的經典題目，解題者不需要使用高難度的資料結構或演算法技巧，只需正確理解問題本身特性之後便可以大幅度降低時間複雜度。
|
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. |
來源：Container With Most Water - LeetCode
問題本身描述很簡單，找出擁有最大蓄水量的邊組合 (兩個邊)。最簡單的方法當然就是暴力法，使用雙迴圈嘗試所有邊組合，不過這樣很顯然會超時，所以接下來就讓我們談談如何將時間複雜度降至 O(n)。
解答：
首先讓我們仔細看看問題所要求的最大蓄水量，該蓄水量與寬度與高度成正比。
如果當下有兩個邊，他們中間的邊高度都低於兩者較低者，那代表中間不存在擁有更大蓄水量的邊組合。因為兩個邊中間寬度必定更窄，當高度也更低時就不可能存在更大的蓄水量。
反之，如果當下有兩個邊，他們中間的高度有高於兩者較低者的邊存在，那中間就有可能出現擁有更大蓄水量的邊組合。
由於兩個邊中間寬度必定更窄，導致蓄水量僅由高度低的邊決定，這時候我們只需要每次移動較低的一邊並計算當下的蓄水量，最後輸出最大值即可找到這個區間內最大的蓄水量。
所以我們可以得出一個時間複雜度為 O(n) 的方法：
- 從最左與最右的兩個邊開始
- 每次移動較低的一邊並計算當下的蓄水量
- 當兩個邊碰頭時即結束，輸出最大值即可找到最大的蓄水量。
|
class Solution {
public:
int maxArea(vector<int>& height) {
int maxWaterArea = 0;
int left = 0;
int right = height.size() - 1;
while (left < right) {
int minHeight = min(height[left], height[right]);
int nowWaterArea = (right - left) * minHeight;
maxWaterArea = max(maxWaterArea, nowWaterArea);
if (height[right] < height[left]) {
right = right - 1;
} else {
left = left + 1;
}
}
return maxWaterArea;
}
};
|
這個方法也被稱作 two pointer，我們只需要紀錄兩個指標以及最大蓄水量，每次根據長短狀況將他們其中一個往中間移動，當所有邊都被看過時，問題便被解決。
常見疑惑：
這個這個方法時常會讓人感到疑惑，在 leetcode 上也有許多討論。
常見的疑惑如上圖，依照 two pointer 方法我們最終會走到 A 組合，但我們完全沒看過 B 組合，是在什麼時候確定 B 組合一定不會更大的？two pointer 是在什麼時候判定那些沒看過的邊組合中不存在更佳解的？
該疑惑的解答其實就是先前一直出現的觀念，two pointer 下兩個邊中間寬度必定更窄，導致蓄水量僅由高度低的邊決定。
長的一邊不論怎麼替換成什麼高度都無法再增加蓄水量，寬度只會越來越窄、高度永遠無法超過低邊的 2。反過來說替換掉短的一邊，雖然寬度一樣變窄，但如果遇到更高邊就有機會獲得更多的容量。所以我們完全不需要考慮移動長邊所產生的組合 (包含 B 組合)，它們之中不可能存在更大的蓄水量。這就是 B 組合可以直接被放棄不需計算的原因。
結語：
我覺得這個題目很有意思才特別寫在部落格，能夠應用 two pointer 來消除掉大量排列組合，是源自於題目本身蓄水量的計算與寬度長度成正比，當其中一方被 two pointer 方法控制住就很容易判斷另一方是否還需要計算。在真實生活也是，我們越是了解問題的本質或特性，就能排除不可能的選項來加速計算甚至直接找出最佳解公式。
參考資料：
[1] Container With Most Water - LeetCode
https://leetcode.com/problems/container-with-most-water/
[2] Yet another way to see what happens in the O(n) algorithm - LeetCode Discuss
留言列表
