Cho một mảng arr chứa thông tin độ cao của các cột. Hãy chọn ra 2 trụ trong mảng để có thể chứa được lượng nước lớn nhất trong tất cả trụ đó, và lượng nước chứa được lớn nhất sẽ là bao nhiêu
Ví dụ:
Với arr = [1,8,6,2,5,4,8,3,7]. Đầu ra maxWater(arr) = 49.
Giải thích: Chọn ra 2 trụ độ cao 8 ở vị trí 1 và 7 ở vị trí 8 thì diện tích thu được lớn nhất là 49.
Đầu vào/Đầu ra:
[Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.
[Đầu vào] Array of integer arr.
2<=arr.size()<=10^5
0<=arr[i]<=10^5
[Đầu ra] Integer
Diện tích nước lớn nhất có thể chứa được.
Python 2:
def maxWater(arr):
left = 0
right = len(arr) – 1
res = 0
while left < right:
res = max(res, min(arr[left], arr[right]) * (right – left))
if arr[left] < arr[right]:
left += 1
else:
right -= 1
return res