Контест Senior Стек и монотонный стек спрашивают часто обновлено
Наибольший прямоугольник в гистограмме
Условие
Гистограмма состоит из n столбцов ширины 1 с высотами h₁ … hₙ, стоящих вплотную. Найдите площадь наибольшего прямоугольника, целиком лежащего внутри гистограммы, со сторонами вдоль осей.
Ввод: в первой строке n (1 ≤ n ≤ 2500), во второй n чисел (0 ≤ hᵢ ≤ 10⁹).
Вывод: максимальная площадь (может не поместиться в 32 бита).
Пример 1
Ввод:
7
2 1 5 6 2 3 1
Вывод:
10
Пример 2
Ввод:
1
0
Вывод:
0
Как подойти
Подсказки: 2
- Зафиксируйте высоту прямоугольника: она равна высоте самого низкого столбца внутри.
- Ближайшие меньшие слева и справа даёт монотонный стек.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.
Предыдущий вопрос
Правильная скобочная последовательность трёх видов
Следующий вопрос
Упростить путь в файловой системе