栈的压入、弹出序列

解题思路：

  1. 定义一个辅助栈 stack；

  2. 遍历 pushed 不断将里面的元素 push 到辅助栈 stack 里面，每 push 一次就判断一下栈顶的元素是不是等于 popped 的对应索引位置的元素；

    • 如果 stack[i] === popped[i]，则 stack 栈顶元素出栈；
    • 如果 stack[i] !== popped[i]，则 stack 继续入栈；

  3. 最后判断 stack 是否为空，为空说明 pushed、popped 是合法序列；

图解：图来自 「k神」

复杂度：

  1. 时间复杂度：O(N)，其中 N 为列表 pushed 的长度；每个元素最多入栈与出栈一次，即最多共 2N 次出入栈操作；

  2. 空间复杂度：O(N)，辅助栈 stack 最多同时存储 N 个元素；

代码实现：

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

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

  return stack.length === 0;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 栈的压入、弹出序列
  2. 2. 解题思路：
  3. 3. 图解：图来自 「k神」
  4. 4. 复杂度：
  5. 5. 代码实现：