946.Validate Stack Sequences
===

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

[946. Validate Stack Sequences](https://leetcode.com/problems/validate-stack-sequences/)

### 題目描述

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

> [name=Ron Chen][time=Thr, 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;
}

> [name=Marsgoat][time=Thr, 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;
}

> [name=Sheep][time=Thr, Apr 13, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)