LeetCode946.验证栈序列 | 刷题打卡

题目描述

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

示例 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.借助一个辅助栈来模拟压入、弹出的过程。

2.设置一个索引idx，记录popV（出栈序列）栈顶的位置

3.将pushV（压入顺序）中的数据依次入栈。

4.当辅助栈栈顶元素和压popV栈顶元素相同时，辅助栈出栈。每次出栈索引idx+1。

5.出栈有可能在任意一次入栈后进行，当辅助栈栈顶元素和压popV栈顶元素相同时，继续让pushV入辅助栈。

6.当所有数据入栈完成，如果出栈顺序正确，那么辅助栈应该为空。

AC代码

var validateStackSequences = function(pushed, popped) {
    let stack = [];
    let i = 0;
    pushed.forEach(element => {
        stack.push(element);
        while (stack.length !== 0 && stack[stack.length - 1] === popped[i]) {
            stack.pop();
            i++;
        }
    });
    return stack.length === 0 ? true : false;
};

总结

模拟push数组的入栈操作，设置一个指针i永远指向下一个要pop出来的元素，如果模拟栈和指针指向的元素相同，就将模拟栈的栈顶元素pop，如果最终可以模拟栈为空，说明可以由push找到pop

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情