Как стать автором
Поиск
Написать публикацию
Обновить

Очень простая структура данных, с помощью которой решаются сложные задачи

Время на прочтение7 мин
Количество просмотров8.4K
Алгоритмы*Спортивное программирование*C++*
Из песочницы

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

Что такое стек?

Стек (англ. stack — "стопка") — это структура данных, работающая по принципу LIFO (Last In, First Out) — "последним пришёл, первым ушёл". Реализация стека приведена во многих языках программирования.

Основные операции со стеком:

  1. push(x) — добавить элемент x на вершину стека.

  2. pop() — удалить верхний элемент.

  3. top() — возвращает верхний элемент без удаления.

  4. empty() — проверка на пустоту (возвращает true/false)

Объяснение принципа работы стека на простом примере

Представьте стопку тарелок, например в кафе

Причем тут вообще стек?

  1. Новую тарелку ставят только наверх стопки.

  2. Взять тарелку можно только сверху (не вытащить из середины, не трогая остальные!).

  3. Видно только верхнюю тарелку (нижние скрыты).

Теперь давайте перейдем к задачам со стеком!

Проверка корректности скобочной последовательности

Условие задачи

Дана строка, содержащая скобки (), [], {}. Нужно определить, является ли расстановка скобок правильной.

Правильная последовательность

  1. Каждой открывающей скобке соответствует закрывающая того же типа.

  2. Скобки закрываются в правильном порядке (последняя открытая — первая закрывается).

Более формально: Пустая последовательность является правильной. Если A — правильная, то последовательности (A), [A], {A} — правильные. Если A и B — правильные последовательности, то последовательность AB — правильная.

Например, последовательности ([{}]) , [()]{}{[()()]()} - правильные, а последовательности ({[}]) , ([)] - нет.

Решение

  1. Создаём пустой стек.

  2. Проходим по строке:

    • Если скобка открывающая — кладём её в стек.

    • Если скобка закрывающая:

      • Проверяем, что стек не пуст (иначе ошибка).

      • Сравниваем её с последней открытой (вершиной стека).

      • Если типы не совпадают — последовательность неправильная.

      • Если совпадают — убираем открывающую скобку из стека.

  3. В конце стек должен быть пустым (все скобки закрыты).

Пример кода на C++

#include <iostream>
#include <stack>
#include <unordered_map>
#include <string>

using namespace std;

int main() {
    string s;
    cin >> s; // вводим строку

    stack<char> st; // создаем пустой стек в котором будем хранить открывающие скобки
    unordered_map<char, char> pairs = {
        {')', '('},
        {']', '['},
        {'}', '{'}
    };
    //для каждой закрывающей скобки храним соответствующую ей открывающую

    bool isValid = true; //здесь храним ответ

    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') { //скобка открывающая
            st.push(c); //добавляем в стек
        } else if (c == ')' || c == ']' || c == '}') { //скобка закрывающая
            if (st.empty() || st.top() != pairs[c]) { //проверяем вершину стека
                isValid = false; //не совпадает
                break;
            }
            st.pop(); //удаляем вершину стека
        }
    }

    if (!st.empty()) { //проверяем что стек пуст
        isValid = false;
    } 
  
    //выводим ответ
    if (isValid){
        cout << "YES";
    } else{
        cout << "NO";
    }

    return 0;
}

Ближайший меньший слева

Условие

Пусть нам дан массив a. Для каждого элемента массива найти индекс ближайшего элемента слева, который меньше текущего. Если такого нет —  -1.

Пример

a = [4, 5, 2, 10, 8]

result = [-1, 0, -1, 2, 2]

Решение

  1. Создаем стек в котором будем хранить индексы элементов массива

  2. Проходим по массиву справа налево:

    • Для каждого элемента a[i]:

      • Пока стек не пуст и a[i] < a[st.top()] (текущий элемент < вершины стека):

        • Обновляем ответ для вершины стека, т.е. result[st.top()] = i

        • Удаляем вершину стека

      • Помещаем i в стек.

Пример кода на C++

#include <iostream>
#include <stack>
using namespace std;

int main() {
	int n;
	cin >> n; //вводим количество элементов в массиве
	int a[n];
	for (int i = 0; i < n; i++){
	    cin >> a[i]; //вводим масив
	}
	int result[n]; //здесь храним ответ для каждого элемента
	for (int i = 0; i < n; i++){
	    result[i] = -1;
	}
	stack<int> st;//стек индексов элементов
	for (int i = n - 1; i >= 0; i--){
	    while (!st.empty() && a[i] < a[st.top()]){
	        result[st.top()] = i; //обновляем ответ для вершины стека
	        st.pop();//удаляем вершину
	    }
	    st.push(i); //добавялем i в стек
	}
	for (int i = 0; i < n; i++){
	    cout << result[i] << ' ';
	} //выводим ответ
    
    return 0;
}

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

Условие

Дана гистограмма (массив высот столбцов). Нужно найти площадь самого большого прямоугольника, который можно вписать в эту гистограмму.

h = [2, 1, 5, 6, 2, 3]
h = [2, 1, 5, 6, 2, 3]

Ответом к этому примеру будет 10. Этот прямоугольник выделен красным цветом.

вписанный прямоугольник
вписанный прямоугольник

Решение

  1. Очевидно, что нижняя сторона итогового прямоугольника будет располагаться на нижнем уровне (на "земле")

  2. Заметим тот факт, что высота итогового прямоугольника всегда будет совпадать с высотой какого-либо столба. Этот факт, я думаю, не нуждается в доказательстве.

Тогда, давайте представим, что мы зафиксировали этот столб. Мы знаем высоту предполагаемого прямоугольника. Она в точности равна высоте столба h[i]. Теперь, осталось разобраться с его шириной.

Представим, что изначально она равна 1 (мы изначально берем в качестве прямоугольника один столб), нам необходимо как-то ее расширить. Допустим, попробуем влево. До каких пор мы можем растягивать ширину влево? До тех пор, пока либо мы не дошли до левой границы или дошли до столба который ниже чем фиксированный. Те же рассуждения справедливы и с правой стороной.

Мы свели задачу к уже раннее решенной. Нам просто нужно посчитать массивы right и left , в которых будут хранится индекс ближайшего меньшего элемента справа и слева для всех столбов. (Для учета индекса ближайшего меньшего элемента справа просто идем наоборот(слева направо)).

То есть, для фиксированного столба i площадь максимального прямоугольника с высотой h[i] будет равна h[i] * (right[i] - left[i] - 1). Ответом будет максимум по всем таким величинам (для всех i).

Пример кода на C++

#include <iostream>
#include <stack>
using namespace std;

int main() {
	int n;
	cin >> n; //вводим количество элементов в массиве
	int h[n];
	for (int i = 0; i < n; i++){
	    cin >> h[i]; //вводим масив
	}
	
	int right[n], left[n];
	for (int i = 0; i < n; i++){
	    right[i] = n, left[i] = -1; //не забываем про учет правой и левой границы
	}
	
	stack<int> st; //стек с индексами
    for (int i = 0; i < n; i++){
        while (!st.empty() && h[i] < h[st.top()]){
            right[st.top()] = i;
            st.pop();
        }
        st.push(i);
    } //считаем right
    
    while (!st.empty()){
        st.pop();
    } //очищаем стек
    
    for (int i = n - 1; i >= 0; i--){
        while (!st.empty() && h[i] < h[st.top()]){
            left[st.top()] = i;
            st.pop();
        }
        st.push(i);
    } //считаем left
    
    int ans = 0; //тут храним ответ
    for (int i = 0; i < n; i++){
        ans = max(ans, h[i] * (right[i] - left[i] - 1));//обновляем ответ
    }
    cout << ans;
    
    return 0;
}

Задача со ВСОШ 2025

Условие

Пусть нам дана матрица a размером n * m в каждой ячейки которой записан 0 или 1. Нам необходимо найти максимальное количество клеток, образующих лестницу в этой матрице.

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

Пример
Пример

Более подробно ознакомиться с условием вы можете по ссылке https://codeforces.com/gym/105842/problem/1

Решение

Давайте посчитаем массив h размером n * m, где h[i][j] - максимальное количество подряд идущих единиц вверх начиная с клетки i,j . Его подсчет очень прост.

  • Если в a[i][j] лежит 0, то h[i][j] = 0

  • Иначе, h[i][j] = h[i - 1][j] + 1

Давайте переберем строку i на которой будет располагаться нижний слой лестницы. Тогда для каждой строки у нас получается массив h размером m (можно сказать, что это гистограмма как в предыдущей задаче).

Будем идти справа налево и поддерживать стек и сумму в нем. Мы должны перебрать каждый столбик в роли "основания" (самого высокого). Как только мы дошли до j столба у нас 2 варианта:

  1. высота j столба больше вершины стека, тогда мы просто добавляем высоту столба в стек и не забываем обновить сумму.

  2. высота j столба меньше или равна вершины стека, мы должны как-то "срубить" нашу лестницу (для того чтобы поддерживать правильный порядок столбов), для этого мы идем пока стек не пуст и высота j столба больше или равна вершины стека. Мы не просто удаляем верхний элемент стека, а нам нужно его заменить на какой-то элемент <= h[j]. Очевидно, нам оптимально взять просто h[j]. Не забываем обновлять сумму.

После каждого изменения суммы обновляем ответ.

Однако, наше решение неэффективно. Оно работает за O(n * m * m) . Для его улучшения, нам необходимо заметить, что в нашем стеке очень много повторяющихся элементов. Поэтому мы можем хранить в стеке не просто числа, а пару чисел, в которой первое - высота, а второе - количество таких высот. Такое решение уже работает O(n * m)

Разберем на примере

Разберем пример (у нас уже зафиксирована строка)

m = 6, h = [2, 1, 5, 6, 2, 3]
m = 6, h = [2, 1, 5, 6, 2, 3]

Изначально стек пуст, сумма sum = 0. Идем справа налево:

  • Встречаем 3, стек пуст, поэтому просто добавляем пару {3, 1} в стек. Прибавляем к сумме 3 * 1 = 3. Итого: sum = 3, st = [{3, 1}]

  • Встречаем 2, 2 < 3. Убираем из стека {3, 1}. Вычитаем из суммы 3 * 1 = 3. Теперь добавляем в стек пару {2, 2} (3 мы заменили на 2). Прибавляем к сумме 2 * 2 = 4. Итого: sum = 4, st = [{2, 2}]

  • Встречаем 6, 6 > 2. Просто кладем в стек {6, 1} и увеличиваем сумму. Итого: sum = 10, st = [{2, 2}, {6, 1}]

  • Встречаем 5, 5 < 6. sum = 14, st = [{2, 2}, {5, 2}]

  • Встречаем 1, 1 < 5, 1 < 2. sum = 5, st = [{5, 1}]

  • Встречаем 2, 2 > 1. sum = 7, st = [{5, 1}, {2, 1}]

Максимальная из всех сумм 14.

Пример кода на C++

#include <iostream>
#include <stack>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); //для этой задачи нужен быстрый ввод
    
	int n;
	cin >> n;
    int m; 
    cin >> m;
    //вводим размеры
    char a[n][m];
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    } //считываем матрицу
    
    int h[n][m];
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            if (a[i][j] == '0'){
                h[i][j] = 0;
            }
            else{
                h[i][j] = 1;
                if (i != 0) h[i][j] += h[i - 1][j];
            }
        }
    } //вычисляем матрицу высот
    
    int ans = 0; //тут храним ответ
    
    for (int i = 0; i < n; i++){ //перебираем строку
        stack<pair<int, int>> st;
        int sum = 0;
        for (int j = m - 1; j >= 0; j--){
            int k = 1; //количество чисел равных h[i][j]
            while (!st.empty() && h[i][j] <= st.top().first){
                sum -= st.top().first * st.top().second; //уменбшаем сумму
                k += st.top().second; //увеличиваем количество равных
                st.pop();
            }
            st.push({h[i][j], k}); //добавляем пару в стек
            sum += h[i][j] * k; //увеличиваем сумму
            ans = max(ans, sum); //обновляем ответ
        }
    }
    
    cout << ans;
    
    return 0;
}

Такое решение получает 100 баллов!

Заключение

Стек — это мощный инструмент, который помогает найти элегантные решения сложных задач.

Если у вас остались какие-то вопросы, не стесняйтесь их задавать https://t.me/vlad1m1r_m

Теги:
Хабы:
+13
Комментарии14
5
Карма
13
Рейтинг
Владимир @vladimir_medvedev

Пользователь

Отправить сообщение

Публикации

Работа

Программист C++
98 вакансий
QT разработчик
5 вакансий

Ближайшие события

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2025, Habr