弹出序列

## 1 题目

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

**示例 1：**

```txt
输入：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：**

```txt
输入：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 的排列。

## 2 问题分析

1. **考虑使用一个辅助栈**，**模拟压入/弹出操作的排列**，**根据是否模拟成功**，**即可得到结果**：

1. **入栈操作**：**按照压栈序列的顺序执行**。
   2. **出栈操作**：**每次入栈后**，**循环判断 `栈顶元素 = 弹出序列的当前元素` 是否成立**，**将符合弹出序列顺序的栈顶元素全部弹出**。
      > 由于题目规定，**栈的所有数字均不相等**，因此**在循环入栈中**，**每个元素出栈的位置的可能性是唯一的**（若有重复数字，则具有多个可出栈的位置），因而，**在遇到 `栈顶元素 = 弹出序列的当前元素` 时就应该立即执行出栈**。
      >
2. 算法流程如下：

1. **初始化**：辅助栈 $stack$，弹出序列的索引 $index$。

![](/media/202206/2022-06-14_110221_872230.png)
   2. **遍历压栈序列**，各元素记为 $num$：

1. 元素 $num$ 入栈。
      2. 循环出栈，若 $stack$ 的栈顶元素 = 弹出序列元素 $popped[index]$，则执行出栈与 $index++$。

![](/media/202206/2022-06-14_110303_305790.png)

![](/media/202206/2022-06-14_110315_645194.png)

![](/media/202206/2022-06-14_110328_346122.png)

![](/media/202206/2022-06-14_110338_984414.png)

![](/media/202206/2022-06-14_110351_209550.png)

![](/media/202206/2022-06-14_110415_874802.png)

![](/media/202206/2022-06-14_110427_833572.png)

![](/media/202206/2022-06-14_110438_865584.png)

![](/media/202206/2022-06-14_110451_401869.png)
   3. **返回值**：若 $stack$ 为空，则此弹出序列合法。

![](/media/202206/2022-06-14_110546_566231.gif)

## 3 参考代码

```java
/**
 * 剑指 Offer 31. 栈的压入、弹出序列
 * @param pushed    压入序列
 * @param popped    弹出序列
 * @return  弹出序列是否是压入序列对应栈的弹出序列
 */
public boolean validateStackSequences(int[] pushed, int[] popped) {
    Stack<Integer> stack = new Stack<>();
    int index = 0;

for (int num: pushed) {
        stack.push(num);
        while (!stack.isEmpty() && stack.peek() == popped[index]) {
            stack.pop();
            index++;
        }
    }

return stack.isEmpty();
}
```

## 参考文献

1. [剑指 Offer 31. 栈的压入、弹出序列](https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof)。
2. [面试题 31. 栈的压入、弹出序列（模拟，清晰图解）](https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/solution/mian-shi-ti-31-zhan-de-ya-ru-dan-chu-xu-lie-mo-n-2)。