题目链接：https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/

1. 题目介绍（31. 栈的压入、弹出序列）

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

【测试用例】：
示例 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 之前弹出。

【条件约束】：

提示：

• 0 <= pushed.length == popped.length <= 1000
• 0 <= pushed[i], popped[i] < 1000
• pushed 是 popped 的排列。

【相关题目】：

注意：本题与主站 946. 验证栈序列 题目相同。

2. 题解

2.1 辅助栈（原书题解）-- O(n)

时间复杂度O(n)，空间复杂度O(n)

解题思路：
一个序列是不是栈的弹出序列的规律：

• 如果下一个弹出的数字刚好是栈顶数字，那么直接弹出；
• 如果下一个弹出的数字不在栈顶，则把压栈序列中还没有入栈的数字要入辅助栈，直到把下一个需要弹出的数字压入栈顶为止；
• 如果所有数字都被压入栈后，仍然没有找到下一个弹出的数字，那么该序列不可能是一个弹出序列。

实现策略：
通过辅助栈和循环去遍历压入和弹出序列，一但在栈中发现符合弹出序列的元素就进行弹出，并将弹出序列下标索引加一，直到循环结束；此时如果栈空则说明全部匹配完毕，非空则说明弹出序列不匹配。

class Solution {public boolean validateStackSequences(int[] pushed, int[] popped) {// 定义辅助栈Stack stack = new Stack<>();// 定义下标索引int popIndex = 0;for(int num : pushed) {stack.push(num); // num 入栈while(!stack.isEmpty() && stack.peek() == popped[popIndex]) { // 循环判断与出栈stack.pop();popIndex++;}}return stack.isEmpty();}
}

3. 参考资料

[1] 面试题31. 栈的压入、弹出序列（模拟，清晰图解）-- 2.1 图片和代码来源