Когда дело доходит до понимания структур данных и алгоритмов, 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();
  }
};

Вот как работает код:

  1. Код определяет класс Solution с общедоступной функцией-членом validateStackSequences, которая принимает два входных параметра: вектор целых чисел, называемый push, и другой вектор целых чисел, называемый popped. Функция возвращает логическое значение.
  2. Внутри функции инициализируется стек целых чисел, называемый стеком.
  3. Целочисленная переменная i также инициализируется значением 0, которое представляет текущий индекс извлеченной последовательности.
  4. Цикл for используется для перебора каждого элемента x в проталкиваемой последовательности.
  5. Внутри цикла текущий элемент x помещается в стек с помощью оператора stack.push(x);.
  6. Цикл while используется для проверки того, равен ли верхний элемент стека текущему элементу в извлеченной последовательности. Используется условие !stack.empty() && stack.top() == popped[i]. Цикл продолжается до тех пор, пока это условие истинно.
  7. Внутри цикла while верхний элемент стека извлекается с помощью оператора stack.pop();. Индексная переменная i также увеличивается с помощью оператора ++i;.
  8. После выхода из цикла while цикл for продолжается со следующим элементом в проталкиваемой последовательности.
  9. После того, как все элементы отправленной последовательности обработаны, функция возвращает 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();
  }
}

Вот как работает этот код:

  1. Код определяет класс Solution с общедоступной функцией-членом validateStackSequences, которая принимает два входных параметра: массив целых чисел с именем push и другой массив целых чисел с именем popped. Функция возвращает логическое значение.
  2. Внутри функции deque (двусторонняя очередь) целых чисел, называемая стеком, инициализируется с помощью оператора Deque<Integer> stack = new ArrayDeque<>();.
  3. Целочисленная переменная i также инициализируется значением 0, которое представляет текущий индекс извлеченной последовательности.
  4. Цикл for-each используется для перебора каждого элемента x в проталкиваемой последовательности.
  5. Внутри цикла текущий элемент x помещается в начало двухсторонней очереди с помощью инструкции stack.push(x);.
  6. Цикл while используется для проверки того, равен ли передний элемент двухсторонней очереди текущему элементу в извлеченной последовательности. Используется условие !stack.isEmpty() && stack.peek() == popped[i]. Цикл продолжается до тех пор, пока это условие истинно.
  7. Внутри цикла while передний элемент двухсторонней очереди извлекается с помощью оператора stack.pop();. Индексная переменная i также увеличивается с помощью оператора ++i;.
  8. После выхода из цикла while цикл for-each продолжается со следующего элемента в проталкиваемой последовательности.
  9. После того, как все элементы отправленной последовательности обработаны, функция возвращает значение 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:

  1. Код определяет класс с именем Solution с общедоступной функцией-членом с именем validateStackSequences, которая принимает два входных параметра: список целых чисел с именем push и другой список целых чисел с именем popped. Функция возвращает логическое значение.
  2. Внутри функции инициализируется пустой список, называемый стеком.
  3. Целочисленная переменная i также инициализируется значением 0, которое представляет текущий индекс извлеченной последовательности.
  4. Цикл for используется для перебора каждого элемента x в проталкиваемой последовательности.
  5. Внутри цикла текущий элемент x добавляется в конец стека с помощью оператора stack.append(x).
  6. Цикл while используется для проверки того, равен ли последний элемент стека текущему элементу в извлеченной последовательности. Используется условие stack and stack[-1] == popped[i]. Цикл продолжается до тех пор, пока это условие истинно.
  7. Внутри цикла while последний элемент стека извлекается с помощью оператора stack.pop(). Индексная переменная i также увеличивается с помощью оператора i += 1.
  8. После выхода из цикла while цикл for продолжается со следующим элементом в проталкиваемой последовательности.
  9. После того, как все элементы отправленной последовательности обработаны, функция возвращает true, если стек пуст, и false в противном случае, используя оператор return not stack.

Заключение:

В заключение, задача № 946 на LeetCode требует от нас проверить, может ли данная выталкиваемая последовательность быть получена из заданной проталкиваемой последовательности с использованием стека. Эта проблема подчеркивает важность понимания структуры данных стека и ее операций. Мы исследовали два разных решения проблемы: одно с использованием стека с явным циклом for, а другое с использованием стека с вложенным циклом while, оба из которых имеют временную сложность O(n). Важно учитывать компромиссы между различными решениями и выбирать наиболее подходящее на основе таких факторов, как временная и пространственная сложность, удобочитаемость и ремонтопригодность. В целом, эта задача проверяет нашу способность анализировать проблемы, разрабатывать и внедрять эффективные алгоритмы и оптимизировать использование структур данных для решения сложных задач.

Проверьте мой Репозиторий Github для решения около 350 проблем LeetCode на разных языках программирования и проверьте мою учетную запись LeetCode здесь.