План курса / Все задачи / Алгоритмы и структуры данных
Самый большой контейнер
средне
# решено
Дан массив целых чисел height, height[i] – высота линии. Нужно найти максимальную площадь, которую может заполнить вода между двумя линиями.
ВАЖНО: площадь воды считается как min(height[i], height[j]) * (j - i), где i – индекс первой линии, а j - номер второй.
Пример 1:
Ввод: height = [1,8,6,2,5,4,8,3,7]
Вывод: 49
Объяснение: 7 * (8 - 1) = 49, "1" - индекс первой линии, "8" - второй
Пример 2:
Ввод: height = [2,3,4,5]
Вывод: 6
Ограничения:
len(height) >= 2
public class Solution
{
public static int MaxArea(IList<int> height)
{
int l = 0;
int r = height.Count - 1;
int resultArea = 0;
while (l < r)
{
// Текущая площадь, ограниченная l и r
int currArea = Math.Min(height[l], height[r]) * (r - l);
// Обновляем максимальную площадь
resultArea = Math.Max(resultArea, currArea);
// Сдвигаем указатель, который указывает на меньшую высоту
if (height[l] < height[r])
{
l++;
}
else
{
r--;
}
}
return resultArea;
}
}
#include <vector>
#include <algorithm>
using namespace std;
int maxArea(vector<int>& height) {
int l = 0;
int r = height.size() - 1;
int resultArea = 0;
while (l < r) {
// текущая площадь, ограниченная l и r
int currArea = min(height[l], height[r]) * (r - l);
// обновляем максимальную площадь
resultArea = max(resultArea, currArea);
// сдвигаем указатель, который указывает на меньшую высоту
if (height[l] < height[r]) {
l++;
} else {
r--;
}
}
return resultArea;
}
package main
func maxArea(height []int) int {
l := 0
r := len(height) - 1
resultArea := 0
for l < r {
// текущая площадь, ограниченная l и r
currArea := min(height[l], height[r]) * (r - l)
// обновляем максимальную площадь
resultArea = max(resultArea, currArea)
// сдвигаем указатель, который указывает на меньшую высоту
if height[l] < height[r] {
l++
} else {
r--
}
}
return resultArea
}
import java.util.*;
public class Solution {
public int maxArea(List<Integer> height) {
int l = 0;
int r = height.size() - 1;
int resultArea = 0;
while (l < r) {
// текущая площадь, ограниченная l и r
int currArea = Math.min(height.get(l), height.get(r)) * (r - l);
// обновляем максимальную площадь
resultArea = Math.max(resultArea, currArea);
// сдвигаем указатель, который указывает на меньшую высоту
if (height.get(l) < height.get(r)) {
l++;
} else {
r--;
}
}
return resultArea;
}
}
from typing import *
def max_area(height: List[int]) -> int:
l = 0
r = len(height) - 1
result_area = 0
while l < r:
# текущая площадь, ограниченная l и r
curr_area = min(height[l], height[r]) * (r - l)
# обновляем максимальную площадь
result_area = max(result_area, curr_area)
# сдвигаем указатель, который указывает на меньшую высоту
if height[l] < height[r]:
l += 1
else:
r -= 1
return result_area
/**
* @param {number[]} height
* @returns {number}
*/
export function maxArea(height) {
let l = 0;
let r = height.length - 1;
let resultArea = 0;
while (l < r) {
// текущая площадь, ограниченная l и r
const currArea = Math.min(height[l], height[r]) * (r - l);
// обновляем максимальную площадь
resultArea = Math.max(resultArea, currArea);
// сдвигаем указатель, который указывает на меньшую высоту
if (height[l] < height[r]) {
l += 1;
} else {
r -= 1;
}
}
return resultArea;
}