946.Validate Stack Sequences

tags: `Medium`,`Array`,`Stack`

題目描述

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.

範例

Example 1:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4),
pop() -> 4,
push(5),
pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Constraints:

1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
All the elements of pushed are unique.
popped.length == pushed.length
popped is a permutation of pushed.

解答

Python
















class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        push_idx, pop_idx, stack = 0, 0, []

        while push_idx < len(pushed) or stack:
            if stack and stack[-1] == popped[pop_idx]:
                stack.pop()
                pop_idx += 1
            else:
                if push_idx < len(pushed):
                    stack.append(pushed[push_idx])
                    push_idx += 1
                else:
                    return False

        return not stack

Ron ChenThr, Apr 13, 2023

Javascript












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

  return stack.length === 0;
}

MarsgoatThr, Apr 13, 2023

TypeScript




















function validateStackSequences(pushed: number[], popped: number[]): boolean {
  const stack: number[] = [];

  function checkTopAndPop(stack: number[]) {
    if (stack[stack.length - 1] === popped[0]) {
      stack.pop();
      popped.shift();
      if (stack.length !== 0) {
        checkTopAndPop(stack);
      }
    }
  }

  pushed.forEach((num) => {
    stack.push(num);
    checkTopAndPop(stack);
  });

  return stack.length === 0;
}

SheepThr, Apr 13, 2023

Reference

回到題目列表