11 - Container With Most Water

解法一 - 暴力法

暴力法就不贅述了,可以看我 這邊記錄 的。

解法二 - Two Pointer

在想出演算法之前,我們需要先學習觀察一些問題的特性:

  1. 以直覺來說,一開始取的 container 是最外側的兩個柱子(分別用 l, r 兩個 pointer 去指),如果要把取的柱子往內移,那 height 必須比原本取的那根柱子高,因為 width 變小了

    以上圖來說,原本 height[l] == 1,height[r] == 7;如果要把 height[l] 往右移,width 就會減少 1,所以會希望 height[l] 變比較高,才有移動的價值。

不過接下來就有一個問題,我們要怎麼決定要內縮 l 還是 r 呢?

最直覺的想法 (Greedy 思維) 就是移動 height 比較小的那邊。因為移動 height 比較小的那邊才會讓面積增加,如果移動 height 比較大的那邊,面積只會註定變小。

所以,如果 height[l] < height[r],就把 l 往右移。反之如果 height[r] < height[l],就把 r 往左移。而如果 height[l] == height[r],就把兩者都往內移。直到兩者相鄰為止。

實做出來的程式碼如下:

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res = INT_MIN, l=0, r=height.size()-1;

        while(l<r) {
            res = max(res, min(height[l], height[r])*(r-l));

            if(height[l] < height[r])
                l++;
            else if(height[l] > height[r])
                r--;
            else{ 
                l++; r--;
            }
        }

        return res;
    }
};

效率頗高!

Runtime: 16 ms, faster than 95.70% of C++ online submissions for Container With Most Water. Memory Usage: 9.7 MB, less than 100.00% of C++ online submissions for Container With Most Water.

results matching ""

    No results matching ""