Алгоритми та структури даних · Middle · Запитання 23 з 75
Яка структура дає вставку й видалення за O(1) з обох кінців?
- 1Збалансоване бінарне дерево пошуку
- ✓Правильна відповідь: Дек (двостороння черга)
- 3Відсортований масив із бінарним пошуком
Пояснення
Дек зазвичай є кільцевим буфером або двозв'язним списком. Це ключова структура для «максимуму в ковзному вікні» за O(n): вона тримає індекси-кандидати в порядку спадання значень.