11. 盛最多水的容器

思路

每次選定兩個柱子，兩個柱子之間可以承裝的水量，是柱子間的距離 x $\min(\small{左柱高, 右柱高})$。

一開始先創建兩個指針left，right，分別指向最左最右， 此時柱子間的距離是最大的。先把答案算一遍，列入參考選項。

接下來要開始移動指針了，兩個指針都在向內移動，代表柱子間的距離會縮短， 此時如果柱高不變，就會損失一些空間，因此在移動指針時， 要盡量移動小的那一邊，因為它更有可能來到更高的柱子，讓容量變得更多。

這個方式不會錯過最佳解。 假設現在最佳解會在left = 2，right = 7的時候被計算出來，兩個指針從左右出發， 會先有一個來到目標位置，比如此時left = 2，right = 9。

• 會錯過答案，就表示此時左指針會繼續往右前進，也就代表 height[2] < height[9]。
• 但如果height[2] < height[9]，它就要比 height[2] 到 height[7] 這個最佳解更好，因為高度都被限制在 height[2]，而前者的寬度更多，這就跟假設矛盾了。

程式碼

雙指針

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int left = 0, right = n - 1;
        int res = 0;
        while(left <= right) {
            if(height[left] < height[right]) { // 移動高度比較矮的柱子對應的指針
                res = max(res, (right - left) * height[left++]);
            }
            else {
                res = max(res, (right - left) * height[right--]);
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$