Алгоритми та структури даних · Senior · Запитання 55 з 75
Що дає монотонний дек у задачі «максимум у ковзному вікні»?
- 1Медіану кожного вікна за O(1)
- ✓Правильна відповідь: Максимум кожного вікна за O(1), O(n) загалом
- 3Відсортовану копію кожного вікна за O(log n)
Пояснення
Дек тримає індекси спадних значень: нові значення знімають менші з кінця, а індекси, що вийшли з вікна, прибираються з початку. Кожен індекс входить і виходить один раз. Для медіани потрібні дві купи.