题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

提示:

• 0 <= pushed.length == popped.length <= 1000
• 0 <= pushed[i], popped[i] < 1000
• pushed 是 popped 的排列。

测试用例

用例1

• 输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
• 输出：true
• 解释：我们可以按以下顺序执行： push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

用例2

• 输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
• 输出：false
• 解释：1 不能在 2 之前弹出。

思路

1. 先把pushed序列压入栈stack，压入一个元素之后与popped第一个元素比较，如果相同，就弹出stack栈顶元素，同时删除popped第一个元素，继续比较，直到两者不同
2. 重复1的操作，直到遍历结束
3. 如果stack为空，则为true，否则为false

代码实现

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入pushed序列");
const pushed = readline().split(",").map(Number);

console.log("请输入popped序列");
const popped = readline().split(",").map(Number);

var validateStackSequences = function (pushed, popped) {
  // 辅助栈来模拟序列的压入
  // 每次与弹出顺序的第一个元素进行比较

  let 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;
};

const res = validateStackSequences(pushed, popped);
console.log("结果为: ", res);

/* 
  请输入pushed序列
  1,2,3,4,5
  请输入popped序列
  4,5,3,2,1
  结果为:  true *

  请输入pushed序列
  1,2,3,4,5
  请输入popped序列
  4,3,5,1,2
  结果为:  false
*/