LC946. 验证栈序列

题目描述

给定 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 <= pushed.length <= 1000 0 <= pushed[i] <= 1000 pushed 的所有元素 互不相同 popped.length == pushed.length popped 是 pushed 的一个排列

题目解析

题目在说什么

这道题其实是在模拟一个“栈”的入栈和出栈过程。栈就像一摞盘子，你只能从最上面拿盘子（后进先出）。题目给了你两个序列：

• pushed：表示你按顺序把数字一个个放进栈里。
• popped：表示你希望按这个顺序把数字从栈里拿出来。

问题是：你能不能通过合理的入栈和出栈操作，正好得到 popped 这个顺序？如果可以，返回 true；不行就返回 false。

举个例子： pushed = [1,2,3,4,5]，popped = [4,5,3,2,1] 你可以先放1、2、3、4，然后拿出4，再放5，拿出5，接着依次拿出3、2、1。这样是可行的，所以答案是 true。

但如果是 popped = [4,3,5,1,2]，你会发现：当你想拿出1的时候，2还压在1上面（因为2比1后放进去），所以拿不到1，答案是 false。

思路是怎么来的

想象你面前有一个空栈，还有一张“操作清单”（pushed）和一张“期望取出顺序清单”（popped）。

你按 pushed 的顺序，一次把一个数字放进栈里。每次放完后，你都可以选择：要不要把栈顶的数字拿出来？拿出来的数字必须和 popped 当前要的那个数字一样。

这个过程就像你在玩一个游戏：

• 你手里有一串数字要放进去（pushed）。
• 你面前有一个空栈。
• 你希望最终拿出来的顺序正好是 popped。

你唯一能做的就是在放数字的间隙，检查栈顶是不是 popped 当前需要的数字，如果是，就立刻拿出来，然后继续看下一个需要的数字。

为什么这样模拟就能判断？因为：

• 栈的特性决定了你只能从顶部拿东西。
• 如果你不立刻拿栈顶那个匹配的数字，它就会被后面的数字压住，以后就拿不到了。
• 所以，只要栈顶匹配，就必须立刻拿，否则顺序就乱了。

这个思路的核心就是：用真实的栈去模拟整个过程，看最后能不能把所有数字都按 popped 的顺序拿出来。

代码逐步拆解

我们来看参考代码，一行一行解释：

Stack<Integer> s = new Stack<Integer>();

• 这里创建了一个空栈 s，用来模拟真实的栈。

int index = 0;

• index 是一个指针，指向 popped 数组的当前位置。一开始我们要拿 popped[0]，所以 index = 0。

for(int i = 0 ; i < pushed.length; i ++){
    s.push(pushed[i]);

• 我们遍历 pushed 数组，把每个数字按顺序放进栈里。这一步就是“入栈操作”。

    while(!s.isEmpty() && popped[index] == s.peek()){
        s.pop();
        index++;
    }
}

• 每次放完一个数字后，我们检查栈顶（s.peek()）是不是等于 popped 当前需要的数字（popped[index]）。
• 如果是，就把它拿出来（s.pop()），同时 index++，表示下一个要拿的数字。
• 这个 while 循环会一直执行，直到栈顶不匹配或者栈空了为止。