Задачи стек (22 октября 2015)

1. [5 минут] Разбор задач на динамику: nearest (наилучшее приближение, расставить плюсы и минусы)
2. [10 минут] Кодинг: дек на циклическом массиве своими руками. Сравнение: чем лучше дек на списках, чем на массиве?
3. [7 минут] Кодинг: двусвязный список с удалением (задача про детей, которые стоят по кругу)
4. [10 минут] Динамический массив (vector): избавимся от амортизации (a[i], push_back)
5. [30 минут] Задачи на стек
1. Несколько типов скобок. Проверить на правильность. Найти парные скобки. O(n).
2. Ближайший слева меньший, ближайший справа меньший за O(n).
3. Массив положительных чисел, ищем отрезок: ∑ × min → max
4. Ищем за O(wh) подподпрямоугольник из нулей максимальной площади в матрице
6. [40 минут] Доп задачи
1. Посчитать по всем отрезкам массива сумму "минимум на отрезке" за O(n)
2. Найти количество подпрямоугольников из нулей в матрице
3. Несколько типов скобок. Найти максимальную по длине подстроку, являющуюся правильной скобочной последовательностью за O(n).
4. По бесконечной прямой в одну сторону идут группы людей, скорость движения группы обратно пропорциональна количеству людей, иногда группы встречаются, тогда объединяются. Сколько в итоге групп останется?
7. [не успеем] Найти k-ю скобочную последовательность из m типов скобок.
8. [не успеем] Разбор выражений стеком