11. Container With Most Water
你被給予一個長度為 n 的整數數組 height。有 n 條垂直線畫出,使得第 i 條線的兩個端點為 (i, 0) 和 (i, height[i])。
找出兩條線,它們與 x 軸一起形成一個容器,使該容器能容納最多的水。
返回容器可以儲存的最大水量。
注意,你不能傾斜容器。
範例 1:
輸入: height = [1,8,6,2,5,4,8,3,7] 輸出: 49 解釋: 上述的垂直線由數組 [1,8,6,2,5,4,8,3,7] 表示。在這種情況下,容器可以容納的最大水量(藍色部分)是 49。
Python
from typing import List
class Solution:
def maxArea(self, height: List[int]) -> int:
# Initialize two pointers, one at the beginning and one at the end of the array
left = 0
right = len(height) - 1
max_water = 0
# Use the two-pointer technique to find the maximum water
while left < right:
# Calculate the width of the current container
width = right - left
# Calculate the height of the container, which is the minimum of the
two heights
current_height = min(height[left], height[right])
# Calculate the area of the container
current_water = width * current_height
# Update the maximum water if the current container holds more water
max_water = max(max_water, current_water)
# Move the pointer that points to the shorter line
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water
29.42MB, 543ms
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxArea(vector<int>& height) {
// Initialize two pointers, one at the beginning and one at the end of the
array
int left = 0;
int right = height.size() - 1;
int max_water = 0;
// Use the two-pointer technique to find the maximum water
while (left < right) {
// Calculate the width of the current container
int width = right - left;
// Calculate the height of the container, which is the minimum of the
two heights
int current_height = min(height[left], height[right]);
// Calculate the area of the container
int current_water = width * current_height;
// Update the maximum water if the current container holds more water
max_water = max(max_water, current_water);
// Move the pointer that points to the shorter line
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return max_water;
}
};
61.43MB, 61ms
Javascript
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
// Initialize two pointers, one at the beginning and one at the end of the array
let left = 0;
let right = height.length - 1;
let max_water = 0;
// Use the two-pointer technique to find the maximum water
while (left < right) {
// Calculate the width of the current container
let width = right - left;
// Calculate the height of the container, which is the minimum of the
two heights
let current_height = Math.min(height[left], height[right]);
// Calculate the area of the container
let current_water = width * current_height;
// Update the maximum water if the current container holds more water
max_water = Math.max(max_water, current_water);
// Move the pointer that points to the shorter line
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return max_water;
};
57.48MB, 57ms