Базовые структуры данных

Кодим

• Дек на циклическом массиве
• Двусвязный список с удалением

Динамический массив (vector): избавимся от амортизации

Задачи на стек

• Несколько типов скобок. Проверить на правильность. Найти парные скобки. \(O(n)\).
• Ближайший слева меньший, ближайший справа меньший за \(O(n)\).
• Массив положительных чисел, ищем отрезок: \(\sum \times \min \rightarrow \max \)
• Ищем за O(wh) подпрямоугольник из нулей максимальной площади в матрице
• Посчитать по всем отрезкам массива сумму минимум на отрезке за \(O(n)\)
• Найти количество подпрямоугольников из нулей в матрице
• Несколько типов скобок. Найти max по длине подстроку, являющуюся правильной скобочной последовательностью за \(O(n)\).

Задача: по бесконечной прямой в одну сторону идут группы людей, скорость движения группы обратно пропорциональна количеству людей, иногда группы встречаются, тогда объединяются. Сколько в итоге групп останется?