剑指offer - 栈的压入弹出序列 - JavaScript

题目描述:输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列 1,2,3,4,5 是某栈的压入顺序,序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列,但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

题目描述

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

解法 1:辅助栈

需要一个辅助栈,来模拟出入栈的过程。算法流程如下:

  • 依次遍历压入序列的元素,检查当前元素和弹出序列的第一个元素是否相等:
    • 若不相等,将元素压入辅助栈
    • 若相等:
      • 元素不入辅助栈,且取出弹出序列的第一个元素。
      • 依次比较弹出序列元素是否和栈元素,批量删除
  • 最后,检查辅助栈和弹出队列是否均为空。

时间复杂度是 O(N^2),空间复杂度是 O(N)。代码实现如下:

// ac地址:https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/
// 原文地址:https://xxoo521.com/2020-01-31-stack-pop-push/

/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
var validateStackSequences = function(pushed, popped) {
    const stack = []; // 辅助栈

    pushed.forEach(v => {
        if (v === popped[0]) {
            popped.shift();
            let i = 0;
            const poppedLength = popped.length;
            for (; i < poppedLength; ++i) {
                if (stack[stack.length - 1] === popped[i]) {
                    stack.pop();
                } else {
                    break;
                }
            }
            popped.splice(0, i);
        } else {
            stack.push(v);
        }
    });

    return !stack.length && !popped.length;
};

更多资料

# ,

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×