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

Кодим

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

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

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

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

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