Сигнал задачи
Когда применять
Доминируемые кандидаты можно навсегда удалить.
Что держать в голове
- Уметь объяснять амортизированную линейную сложность.
- Уметь выбирать индексы вместо значений, когда важна позиция.
- Уметь поддерживать максимум скользящего окна монотонным деком.
Сложность
- Каждый элемент добавляется и удаляется не более одного раза: O(n) времени и O(n) памяти в худшем случае.
Границы и ошибки
- Направление монотонности и политика равных значений определяют, ищется ли строго больший или не меньший элемент.