57 lines
1.2 KiB
Python
57 lines
1.2 KiB
Python
"""
|
||
Дан массив целых чисел nums, nums[i] – высота линии. Нужно найти максимальную площадь, которую может заполнить вода между двумя линиями.
|
||
|
||
ВАЖНО: площадь воды считается как min(nums[i], nums[j]) * (j - i), где i – индекс первой линии, а j - номер второй.
|
||
|
||
Пример 1:
|
||
Ввод: nums = [1,8,6,2,5,4,8,3,7]
|
||
Вывод: 49
|
||
Объяснение: 7 * (8 - 1) = 49, "1" - индекс первой линии, "8" - второй
|
||
|
||
Пример 2:
|
||
Ввод: nums = [2,3,4,5]
|
||
Вывод: 6
|
||
|
||
Ограничения:
|
||
len(nums) >= 2
|
||
|
||
i j
|
||
2,3,4,5
|
||
0 1 2 3
|
||
|
||
cur_max = 2 * 3 = 6
|
||
1: двигаем i
|
||
|
||
i j
|
||
2,3,4,5
|
||
0 1 2 3
|
||
|
||
cur_max = 3 * 2 = 6
|
||
1: двигаем i
|
||
|
||
|
||
i j
|
||
2,3,4,5
|
||
0 1 2 3
|
||
|
||
cur_max = 4 * 1 = 4
|
||
|
||
"""
|
||
|
||
def solve(nums):
|
||
max = 0
|
||
i = 0
|
||
j = len(nums) - 1
|
||
while i < j:
|
||
cur_max = min(nums[i], nums[j]) * (j - i)
|
||
if cur_max > max:
|
||
max = cur_max
|
||
if nums[i] <= nums[j]:
|
||
i += 1
|
||
else:
|
||
j -= 1
|
||
return max
|
||
|
||
|
||
print(f"exp 49, got: {solve([1,8,6,2,5,4,8,3,7])}")
|
||
print(f"exp 6, got: {solve([2,3,4,5])}")
|