Код Senior Стек и монотонный стек обновлено
Сколько воды удержится
Условие
Массив высот столбиков. Сколько единиц воды задержится между ними после дождя?
Примеры
trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) // 6
trap([4, 2, 0, 3, 2, 5]) // 9
trap([]) // 0
Как подойти
Решение через два массива префиксных максимумов даёт O(n) памяти. Два указателя дают O(1): если левый столбик ниже правого, то ограничение слева уже определено, и правый максимум роли не играет. Это одна из самых часто задаваемых задач на монотонность.
Подсказки: 2
- Над каждым столбиком воды столько, сколько даёт минимум из максимумов слева и справа.
- Двигать выгодно ту сторону, где столбик ниже: там ограничение уже известно.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.