946. Validate Stack Sequences

leetcode medium

#array#csharp#leetcode#medium#stack

Task

Учитывая, что два целочисленных массива pushed и popped имеют разные значения, верните true, если это могло быть результатом последовательности операций push и pop на изначально пустом стеке, или false в противном случае.

Пример:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

Output: true

C# solution

matched/original

public class Solution {
    public bool ValidateStackSequences(int[] pushed, int[] popped) {
        Stack<int> stack = new Stack<int>();
        int j = 0;
        foreach (int x in pushed) {
            stack.Push(x);
            while (stack.Count > 0 && j < popped.Length && stack.Peek() == popped[j]) {
                stack.Pop();
                j++;
            }
        }
        return j == popped.Length;
    }
}

C++ solution

auto-draft, review before submit

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool ValidateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> stack = new stack<int>();
        int j = 0;
        foreach (int x in pushed) {
            stack.push(x);
            while (stack.size() > 0 && j < popped.size() && stack.Peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return j == popped.size();
    }
}

Java solution

matched/original

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int x : pushed) {
            stack.push(x);
            while (!stack.isEmpty() && j < popped.length && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return j == popped.length;
    }
}

JavaScript solution

matched/original

var validateStackSequences = function(pushed, popped) {
    const stack = [];
    let j = 0;
    for (let x of pushed) {
        stack.push(x);
        while (stack.length && j < popped.length && stack[stack.length - 1] === popped[j]) {
            stack.pop();
            j++;
        }
    }
    return j === popped.length;
};

Python solution

matched/original

def validateStackSequences(pushed, popped):
    stack = []
    j = 0
    for x in pushed:
        stack.append(x)
        while stack and j < len(popped) and stack[-1] == popped[j]:
            stack.pop()
            j += 1
    return j == len(popped)

Go solution

matched/original

package main

func validateStackSequences(pushed []int, popped []int) bool {
    stack := []int{}
    j := 0
    for _, x := range pushed {
        stack = append(stack, x)
        for len(stack) > 0 && j < len(popped) && stack[len(stack)-1] == popped[j] {
            stack = stack[:len(stack)-1]
            j++
        }
    }
    return j == len(popped)
}

Explanation

Algorithm

Инициализировать пустой стек.

Использовать указатель j для отслеживания текущей позиции в массиве popped.

Пройти по каждому элементу в массиве pushed:

Добавить элемент в стек.

Проверить верхний элемент стека:

Если он совпадает с текущим элементом в popped, удалить элемент из стека и увеличить указатель j.

В конце вернуть true, если указатель j достиг конца массива popped, иначе вернуть false.

😎