Наибольший прямоугольник гистограммы
Hard
Дана гистограмма: столбцы ширины 1 и высоты
heights[i]. Найдите максимальный по площади прямоугольник, составленный из соседних столбцов. Высота такого прямоугольника не может превышать самый низкий столбец в выбранном диапазоне.heights: 2 1 5 6 2 3
██ ██
██ ██ ██ ██
██ ██ ██ ██ ██ ██
площадь 5×2 = 10 (столбцы высот 5 и 6)Примеры:
Вход:
[2, 1, 5, 6, 2, 3]
Выход:
10
Объяснение: [2,1,5,6,2,3]: прямоугольник на столбцах высот 5 и 6 имеет высоту 5 и ширину 2, площадь 10 — это максимум.
Вход:
[2, 4]
Выход:
4
Объяснение: [2,4]: можно взять оба столбца высотой min(2,4)=2 и шириной 2 (площадь 4) или один столбец высоты 4 (площадь 4). Ответ 4.
Вход:
[1]
Выход:
1
Объяснение: [1]: единственный столбец даёт прямоугольник площади 1.
Ограничения:
1 <= heights.length <= 10^5
Комментарии (0)
Войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!