runtime 96 ms, beats 94.68% of cpp submissions
O(n) solution with explanation

tags: two pointer

Container With Most Water

📖 description

給定一個代表牆高的陣列，求任兩座牆之間的最大面積。

ex.
    height = [1,8,6,2,5,4,8,3,7]
    最大面積為 min(8,7) * (8-1)，由 height[1] 與 height[8] 組成

    min(8,7) 表示面積的高
    (8-1)    表示兩座牆的距離

🧠 solution

利用雙指標一個指向開頭一個指向結尾，並維護當前看到的最大面積

  • 如果 height[l] < height[r] ，則我們期望留下 height[r] ，所以 l++
  • 反之，我們期望留下 height[l] ，所以 r–

可以在移動指標時把終止條件設為看到比目前大的才停止，以節省運算次數

⏳ time complexity

遍歷一次陣列，時間複雜度 O(n)
總時間複雜度 O(n)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxArea(vector<int>& height) {
        int area = 0;
        int l = 0, r = height.size()-1;
        while(r>l){
            area = max(area,min(height[l],height[r])*(r-l));  // 維護當前最大面積
            if(height[l]<height[r]){                          // 把較小的牆往內移
                l++;
                while(height[l-1]>height[l]) l++;             // 減少運算次數
            }
            else{
                r--;
                while(height[r+1]>height[r]) r--;
            }
        }
        return area;
    }
};