946.验证栈序列

验证栈序列

给定 pushed 和 popped 两个序列，每个序列中的值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false。

示例 1:

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true

示例 2:

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false

提示:

• 0 <= pushed.length <= 1000
• 0 <= popped.length <= 1000
• pushed 是 popped 的排列

解析

模拟栈的 push 和 pop 操作，将 pushed 入栈，同时检查栈顶是否等于 popped 的当前元素。

var validateStackSequences = function (pushed, popped) {
  const stack = [];
  let j = 0;

  for (const x of pushed) {
    stack.push(x);
    while (stack.length && stack[stack.length - 1] === popped[j]) {
      stack.pop();
      j++;
    }
  }

  return stack.length === 0;
};

时间复杂度 O(n)，空间复杂度 O(n)。