[LeetCode] 946. Validate Stack Sequences 刷題筆記
Cathy P
 2022-03-22 22:34:21      

題目

LeetCode 連結：
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.

題目會給一個 pushed 的數值陣列和一個 popped 的數值陣列。我們需要驗證這兩個陣列是否順序的 push 和 pop 同一個 Stack。

Example 1:

1
2
3
4
5
6
7
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:

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

解題過程

看到題目我第一個想法就是直接透過模擬一個 stack push 和 pop 的過程，來判斷是不是合理的。

  1. 建立一個 stack 陣列。
  2. 將 pushed 的數值依序 push 進 stack 中。
  3. 若 stack 中的最後一個值與 popped[0]的值相同，則將 stack 最後一個值 pop 出來，並將 popped 的第一個值移出。
  4. 所有 pushed 的數值都放進 arr 之後，依序驗證 arr 的最後一個值和 popped[0]的值是否相同。
    如果不相同則回傳 false，相同則將 stack 最後一個值 pop 出來，並將 popped 的第一個值移出。
  5. stack 的值全部被 pop 出回傳成功。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
var validateStackSequences = function (pushed, popped) {
  let stack = [];
  while (pushed.length !== 0) {
    if (stack.length > 0 && stack[stack.length - 1] === popped[0]) {
      stack.pop();
      popped.shift();
    } else {
      stack.push(pushed.shift());
    }
  }
  while (popped.length !== 0 && stack.length !== 0) {
    if (stack[stack.length - 1] === popped[0]) {
      stack.pop();
      popped.shift();
    } else {
      return false;
    }
  }
  return true;
};

成績

Runtime: 67 ms (排名：87.77%)
Memory Usage: 43.6 MB (排名：71.89%)