8.2 Ближайшие меньшие элементы

Во многих задачах нужно для каждого элемента массива быстро найти первый меньший элемент слева. Эту задачу удобно решать с помощью стека, а её линейная сложность хорошо объясняется через амортизированный анализ.

Постановка задачи

Дан массив. Для каждого его элемента нужно найти ближайший меньший элемент, который стоит левее.

Если такого элемента нет, нужно сообщить об этом отдельно.

Например, для массива:

2 5 7 3 6 4 8 3

ответы будут такими:

• для 2 — нет меньшего слева;
• для 5 — 2;
• для 7 — 5;
• для 3 — 2;
• для 6 — 3;
• для 4 — 3;
• для 8 — 4;
• для 3 — 2.

Идея

Будем идти по массиву слева направо и поддерживать стек.

В стеке хранятся кандидаты, которые ещё могут оказаться ближайшими меньшими для будущих элементов.

Когда мы рассматриваем очередной элемент x:

1. Пока стек не пуст и его верхушка не меньше x, удаляем верхушку.

2. После этого:

3. если стек пуст, меньшего элемента слева нет;

4. иначе верхушка стека и есть ближайший меньший элемент.
5. Затем кладём x в стек.

Почему это работает? Потому что все элементы, которые не могут быть ответом ни для текущего, ни для будущих элементов, мы сразу убираем.

Пошаговый пример

Рассмотрим массив:

2 5 7 3 6 4 8 3

Шаг 1: элемент 2

Стек пуст, значит меньшего слева нет.

После этого кладём 2 в стек.

Стек: 2

Шаг 2: элемент 5

Верхушка стека — 2, а 2 < 5, значит это ближайший меньший элемент.

Кладём 5 в стек.

Стек: 2 5

Шаг 3: элемент 7

Верхушка — 5, и 5 < 7, значит ответ для 7 — это 5.

Кладём 7 в стек.

Стек: 2 5 7

Шаг 4: элемент 3

Теперь верхушка 7 не подходит, потому что 7 >= 3 — удаляем.

Потом 5 >= 3 — тоже удаляем.

Теперь на вершине 2, и 2 < 3. Значит, ближайший меньший для 3 — это 2.

Кладём 3 в стек.

Стек: 2 3

Шаг 5: элемент 6

Верхушка 3, а 3 < 6, значит ответ — 3.

Кладём 6 в стек.

Стек: 2 3 6

Шаг 6: элемент 4

6 >= 4, значит 6 удаляем.

Теперь на вершине 3, и 3 < 4, значит ответ — 3.

Кладём 4 в стек.

Стек: 2 3 4

Шаг 7: элемент 8

Верхушка 4, и 4 < 8, значит ответ — 4.

Кладём 8 в стек.

Стек: 2 3 4 8

Шаг 8: элемент 3

8 >= 3 — удаляем.

4 >= 3 — удаляем.

3 >= 3 — тоже удаляем, потому что нужен именно меньший, а не меньший или равный.

Теперь на вершине 2, и 2 < 3, значит ответ — 2.

Кладём 3 в стек.

Стек: 2 3

Почему алгоритм работает быстро

На первый взгляд кажется, что цикл с удалениями может сделать алгоритм медленным. Ведь в одном шаге мы можем удалить сразу много элементов.

Но здесь как раз и применяется амортизированный анализ.

Каждый элемент массива:

• ровно один раз добавляется в стек;
• не более одного раза удаляется из стека.

Значит, суммарно по всему алгоритму будет:

• n добавлений;
• не более n удалений.

Итого все операции со стеком занимают O(n).

То есть, несмотря на внутренний цикл while, общая сложность алгоритма остаётся линейной.

Сложность

• Время: O(n)
• Память: O(n)

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {2, 5, 7, 3, 6, 4, 8, 3};
    stack<int> st;

    for (int x : a) {
        while (!st.empty() && st.top() >= x) {
            st.pop();
        }

        if (st.empty()) {
            cout << x << ": нет меньшего слева\n";
        } else {
            cout << x << ": " << st.top() << "\n";
        }

        st.push(x);
    }
}

Если нужны индексы, а не значения

Во многих задачах требуется вывести не сам ближайший меньший элемент, а его позицию.

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

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {2, 5, 7, 3, 6, 4, 8, 3};
    stack<int> st; // храним индексы

    for (int i = 0; i < (int)a.size(); i++) {
        while (!st.empty() && a[st.top()] >= a[i]) {
            st.pop();
        }

        if (st.empty()) {
            cout << "Для позиции " << i << " ответа нет\n";
        } else {
            cout << "Для позиции " << i << " ближайший меньший индекс: "
                 << st.top() << ", значение: " << a[st.top()] << "\n";
        }

        st.push(i);
    }
}

Что важно запомнить

• Мы идём по массиву слева направо.
• В стеке поддерживаем возрастающую последовательность значений.
• Всё, что не может стать ответом в будущем, сразу удаляем.
• Каждый элемент входит в стек и выходит из него не более одного раза.
• Поэтому итоговая сложность — O(n).

Где это применяется

Эта техника регулярно встречается в задачах на:

• ближайший меньший или больший элемент;
• максимальный прямоугольник в гистограмме;
• обработку отрезков;
• монотонные стек и очередь;
• оптимизации с амортизированным анализом.

Такой стек часто называют монотонным стеком, потому что он поддерживает специальный порядок элементов.