給定一個長度為 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;
}
};