Leetcode 11. Container With Most Water

Container With Most Water :

給定一個長度為 n 的整數數組高度。 繪製了 n 條垂直線，使得第 i 條線的兩個端點是 (i, 0) 和 (i, height[i])。找到兩條線，它們與 x 軸一起形成一個容器，使得容器中的水最多(最大的含水量)

Python

雙指針求解

一個從最左邊開始，一個從最右邊開始，計算兩個擋板之間的面積，然後在向中間移動，如果哪個擋板比較矮，就捨棄掉這個擋板，把指向這個擋板的指針向中間移動。這樣每次都能保留了比較長的哪個擋板，獲得更多的水。

時間複雜度: O(n)

空間複雜度: O(1)

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxarea=0
        l=0
        r=len(height)-1
        while(l<r):
            maxarea=max(maxarea,min(height[l], height[r])*(r-l))
            if height[r]>height[l]:
                l+=1
            else:
                r-=1
        return maxarea

C++

雙指標(two pointers)

class Solution {
public:
    int maxArea(const vector<int>& height) {
        int ans = 0;
        int l = 0;
        int r = height.size() - 1;
        while (l < r) {
            int h = min(height[l], height[r]);
            ans = max(ans, h * (r - l));
            if (height[l] < height[r]) 
                ++l;
            else
                --r;
        }
        return ans;
    }
};