Стек ближайших меньших

Для каждого элемента найти ближайший слева, который меньше его. В лоб — $O(n^2)$. Со стеком — линия, и это тот случай, когда линейность неочевидна.

Инвариант

В стеке лежат индексы, а значения по ним строго возрастают снизу вверх.

vector<int> stack;
for (int i = 0; i < n; i++) {
    while (!stack.empty() && a[stack.back()] >= a[i]) stack.pop_back();
    left[i] = stack.empty() ? -1 : stack.back();   // ближайший меньший слева
    stack.push_back(i);
}

Почему можно выбрасывать? Если пришёл элемент, не больший вершины, то вершина никогда больше не пригодится: для всего, что правее, она перекрыта новым — и он меньше, и он ближе.

Каждый индекс кладётся один раз и снимается не больше одного раза. Значит, тело внутреннего цикла выполняется суммарно не больше $n$ раз — снова амортизация.

Строгость сравнения

>= или > в условии выброса — не вкусовщина. От этого зависит, что считается «ближайшим меньшим» при равных значениях, и в задачах на подсчёт это меняет ответ.

Правило: если равные элементы должны считаться один раз, с одной стороны берут строгое сравнение, с другой — нестрогое. Проверяется это не рассуждением, а перебором на массиве из повторов.

Три задачи, один стек

Куда переселятся жители

Для каждого города найти ближайший восточнее, где жить дешевле. Это ровно то, что стек и даёт — только смотрим направо:

vector<int> answer(n, -1), stack;
for (int i = 0; i < n; i++) {
    while (!stack.empty() && a[stack.back()] > a[i]) {
        answer[stack.back()] = i;      // для этого города нашёлся ответ
        stack.pop_back();
    }
    stack.push_back(i);
}
// кто остался в стеке — тем ответа нет

Обратите внимание на смену роли: здесь ответ записывается в момент выброса, а не в момент прихода.

Наибольший прямоугольник в гистограмме

Когда столбик снимается со стека, становятся известны обе его границы: слева — новая вершина стека, справа — текущий индекс. Значит, в этот момент известна максимальная ширина прямоугольника такой высоты.

for (int i = 0; i <= n; i++) {
    int current = (i == n) ? -1 : h[i];       // сторож в конце
    while (!stack.empty() && h[stack.back()] >= current) {
        long long height = h[stack.back()];
        stack.pop_back();
        int leftBound = stack.empty() ? -1 : stack.back();
        best = max(best, height * (i - leftBound - 1));
    }
    stack.push_back(i);
}

Сторож с высотой $-1$ в конце нужен, чтобы стек гарантированно опустел и все столбики получили свою правую границу.

Наибольший прямоугольник из белых клеток

Та же гистограмма, но построенная заново для каждой строки таблицы: высота столбца — сколько белых клеток подряд идёт вверх от текущей строки. Один проход по строке даёт ответ для всех прямоугольников, нижняя граница которых в ней. Итого $O(NM)$ на всю таблицу.

Сумма минимумов

Приём считает не только сам ответ, но и сколько отрезков имеет данный минимум. Если для элемента $i$ известны ближайший меньший слева $L$ и справа $R$, то он является минимумом ровно на $(i - L) \cdot (R - i)$ отрезках.

Отсюда сумма минимумов по всем отрезкам считается за линию. Именно здесь строгость сравнений критична: слева нужно строгое, справа нестрогое (или наоборот), иначе отрезки с повторяющимся минимумом посчитаются дважды.