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

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

• 取压入队列的首元素，将其压入辅助栈
• 检查辅助栈顶元素是否和弹出队列的首元素相等：
  • 若相等，则辅助栈弹出栈顶元素，弹出队列取出队首元素，重复检查
  • 若不相等，回到第一步

最后，检查辅助栈和弹出队列是否均为空。

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

// ac地址：https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106
// 原文地址：https://xxoo521.com/2020-01-31-stack-pop-push/

/**
 *
 * @param {string[]} pushV
 * @param {string[]} popV
 */
function IsPopOrder(pushV, popV) {
    const stack = []; // 辅助栈

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

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

🔍<stron>公众号「心谭博客」</stron>

🔍查看「前端图谱」&「算法题解」