Когда дело доходит до понимания структур данных и алгоритмов, Leetcode является одним из лучших онлайн-ресурсов. Обладая обширной библиотекой задач, которые необходимо решить, он предоставляет разработчикам широкие возможности для практики своих навыков программирования и изучения новых методов. В этой статье мы обсудим одну из таких задач от Leetcode — задачу № 946 «Проверить последовательности стека».
Постановка задачи :
Имея две последовательности push и pop с различными значениями, возвращайте true тогда и только тогда, когда это могло быть результатом последовательности операций push и pop в изначально пустом стеке.
Давайте разберем постановку задачи и поймем, что она означает. Проблема, по сути, состоит в том, чтобы определить, допустима ли заданная последовательность операций push и pop в изначально пустом стеке. Нам даны две последовательности — последовательность элементов, помещенных в стек, и последовательность элементов, извлеченных из стека. Значения в обеих последовательностях различны. Наша задача состоит в том, чтобы определить, представляют ли данные последовательности допустимую последовательность операций push и pop.
Подход:
Чтобы решить эту проблему, мы можем использовать структуру данных стека. Мы можем помещать элементы из помещенной последовательности в стек до тех пор, пока вершина стека не будет равна первому элементу извлеченной последовательности. Как только вершина стека сравняется с первым элементом в извлеченной последовательности, мы можем извлекать элементы из стека до тех пор, пока вершина стека не перестанет равняться первому элементу в извлеченной последовательности. Затем мы можем повторять этот процесс до тех пор, пока не будут обработаны все элементы в извлеченной последовательности. Если мы можем обработать все элементы в извлеченной последовательности, то данные последовательности представляют собой допустимую последовательность операций вталкивания и извлечения.
Алгоритм:
Давайте возьмем пример, чтобы понять это лучше. Рассмотрим следующий ввод:
нажал = [1,2,3,4,5] вытолкнул = [4,5,3,2,1]
Мы можем использовать стек для отслеживания элементов, помещенных в стек. Мы будем помещать элементы из помещенной последовательности в стек до тех пор, пока вершина стека не будет равна первому элементу извлеченной последовательности. В этом случае мы помещаем в стек элементы 1, 2, 3 и 4. Как только вершина стека становится равной 4, мы начинаем извлекать элементы из стека до тех пор, пока вершина стека больше не будет равна 4. Мы извлекаем элементы 4 и 5 из стека. Стек теперь содержит элементы 1, 2 и 3. Первым элементом в извлеченной последовательности теперь является 3, что равно вершине стека. Мы повторяем тот же процесс помещения элементов в стек до тех пор, пока вершина стека не станет равной 2, а затем извлекаем элементы из стека до тех пор, пока вершина стека не перестанет равняться 2. Мы извлекаем элемент 2 из стека. Стек теперь содержит элементы 1 и 3. Первым элементом в извлеченной последовательности теперь является 2, что равно вершине стека. Мы повторяем тот же процесс помещения элементов в стек до тех пор, пока вершина стека не станет равной 1, а затем извлекаем элементы из стека до тех пор, пока вершина стека не перестанет равняться 1. Мы извлекаем элементы 1 и 3 из стека. куча. Теперь стек пуст, и мы обработали все элементы извлеченной последовательности. Следовательно, данные последовательности представляют собой допустимую последовательность операций push и pop.
Псевдокод:
function validateStackSequences(pushed, popped) stack = new Stack() i = 0 // index of popped sequence for each element x in pushed stack.push(x) // push element onto stack while stack is not empty and stack.top() == popped[i] stack.pop() // pop element from stack i = i + 1 // increment index of popped sequence return stack is empty // return true if stack is empty, false otherwise
Алгоритм использует структуру данных стека для отслеживания элементов, помещаемых в стек, и индексную переменную i для отслеживания текущей позиции в извлеченной последовательности. Цикл for перебирает каждый элемент в проталкиваемой последовательности и помещает его в стек. Цикл while проверяет, равен ли верхний элемент стека текущему элементу извлеченной последовательности. Если это так, то элемент извлекается из стека, а индексная переменная i увеличивается. Алгоритм возвращает true, если стек пуст, и false в противном случае.
Сложность времени:
Временная сложность этого алгоритма равна O(n), где n — длина входных последовательностей. Это связано с тем, что мы перебираем каждый элемент во входных последовательностях ровно один раз.
Решение:
C++
class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { stack<int> stack; int i = 0; // popped's index for (const int x : pushed) { stack.push(x); while (!stack.empty() && stack.top() == popped[i]) { stack.pop(); ++i; } } return stack.empty(); } };
Вот как работает код:
- Код определяет класс Solution с общедоступной функцией-членом validateStackSequences, которая принимает два входных параметра: вектор целых чисел, называемый push, и другой вектор целых чисел, называемый popped. Функция возвращает логическое значение.
- Внутри функции инициализируется стек целых чисел, называемый стеком.
- Целочисленная переменная i также инициализируется значением 0, которое представляет текущий индекс извлеченной последовательности.
- Цикл for используется для перебора каждого элемента x в проталкиваемой последовательности.
- Внутри цикла текущий элемент x помещается в стек с помощью оператора
stack.push(x);
. - Цикл while используется для проверки того, равен ли верхний элемент стека текущему элементу в извлеченной последовательности. Используется условие
!stack.empty() && stack.top() == popped[i]
. Цикл продолжается до тех пор, пока это условие истинно. - Внутри цикла while верхний элемент стека извлекается с помощью оператора
stack.pop();
. Индексная переменная i также увеличивается с помощью оператора++i;
. - После выхода из цикла while цикл for продолжается со следующим элементом в проталкиваемой последовательности.
- После того, как все элементы отправленной последовательности обработаны, функция возвращает true, если стек пуст, и false в противном случае, используя оператор
return stack.empty();
.
В целом, алгоритм использует стек для отслеживания элементов, помещаемых в стек, и проверяет, находятся ли элементы, извлеченные из стека, в правильном порядке, используя индексную переменную i. Временная сложность этого алгоритма равна O(n), где n — длина входных последовательностей, поскольку мы итерируем каждый элемент во входных последовательностях ровно один раз.
Ява
class Solution { public boolean validateStackSequences(int[] pushed, int[] popped) { Deque<Integer> stack = new ArrayDeque<>(); int i = 0; // popped's index for (final int x : pushed) { stack.push(x); while (!stack.isEmpty() && stack.peek() == popped[i]) { stack.pop(); ++i; } } return stack.isEmpty(); } }
Вот как работает этот код:
- Код определяет класс Solution с общедоступной функцией-членом validateStackSequences, которая принимает два входных параметра: массив целых чисел с именем push и другой массив целых чисел с именем popped. Функция возвращает логическое значение.
- Внутри функции deque (двусторонняя очередь) целых чисел, называемая стеком, инициализируется с помощью оператора
Deque<Integer> stack = new ArrayDeque<>();
. - Целочисленная переменная i также инициализируется значением 0, которое представляет текущий индекс извлеченной последовательности.
- Цикл for-each используется для перебора каждого элемента x в проталкиваемой последовательности.
- Внутри цикла текущий элемент x помещается в начало двухсторонней очереди с помощью инструкции
stack.push(x);
. - Цикл while используется для проверки того, равен ли передний элемент двухсторонней очереди текущему элементу в извлеченной последовательности. Используется условие
!stack.isEmpty() && stack.peek() == popped[i]
. Цикл продолжается до тех пор, пока это условие истинно. - Внутри цикла while передний элемент двухсторонней очереди извлекается с помощью оператора
stack.pop();
. Индексная переменная i также увеличивается с помощью оператора++i;
. - После выхода из цикла while цикл for-each продолжается со следующего элемента в проталкиваемой последовательности.
- После того, как все элементы отправленной последовательности обработаны, функция возвращает значение true, если двухсторонняя очередь пуста, и значение false в противном случае, используя оператор
return stack.isEmpty();
.
В целом, алгоритм использует двухстороннюю очередь для отслеживания элементов, помещаемых в стек, и проверяет, находятся ли элементы, извлеченные из стека, в правильном порядке, используя индексную переменную i. Временная сложность этого алгоритма равна O(n), где n — длина входных последовательностей, поскольку мы итерируем каждый элемент во входных последовательностях ровно один раз.
Питон
class Solution: def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool: stack = [] i = 0 # popped's index for x in pushed: stack.append(x) while stack and stack[-1] == popped[i]: stack.pop() i += 1 return not stack
Вот объяснение данного кода Python:
- Код определяет класс с именем Solution с общедоступной функцией-членом с именем validateStackSequences, которая принимает два входных параметра: список целых чисел с именем push и другой список целых чисел с именем popped. Функция возвращает логическое значение.
- Внутри функции инициализируется пустой список, называемый стеком.
- Целочисленная переменная i также инициализируется значением 0, которое представляет текущий индекс извлеченной последовательности.
- Цикл for используется для перебора каждого элемента x в проталкиваемой последовательности.
- Внутри цикла текущий элемент x добавляется в конец стека с помощью оператора
stack.append(x)
. - Цикл while используется для проверки того, равен ли последний элемент стека текущему элементу в извлеченной последовательности. Используется условие
stack and stack[-1] == popped[i]
. Цикл продолжается до тех пор, пока это условие истинно. - Внутри цикла while последний элемент стека извлекается с помощью оператора
stack.pop()
. Индексная переменная i также увеличивается с помощью оператораi += 1
. - После выхода из цикла while цикл for продолжается со следующим элементом в проталкиваемой последовательности.
- После того, как все элементы отправленной последовательности обработаны, функция возвращает true, если стек пуст, и false в противном случае, используя оператор
return not stack
.
Заключение:
В заключение, задача № 946 на LeetCode требует от нас проверить, может ли данная выталкиваемая последовательность быть получена из заданной проталкиваемой последовательности с использованием стека. Эта проблема подчеркивает важность понимания структуры данных стека и ее операций. Мы исследовали два разных решения проблемы: одно с использованием стека с явным циклом for, а другое с использованием стека с вложенным циклом while, оба из которых имеют временную сложность O(n). Важно учитывать компромиссы между различными решениями и выбирать наиболее подходящее на основе таких факторов, как временная и пространственная сложность, удобочитаемость и ремонтопригодность. В целом, эта задача проверяет нашу способность анализировать проблемы, разрабатывать и внедрять эффективные алгоритмы и оптимизировать использование структур данных для решения сложных задач.
Проверьте мой Репозиторий Github для решения около 350 проблем LeetCode на разных языках программирования и проверьте мою учетную запись LeetCode здесь.