> For the complete documentation index, see [llms.txt](https://ryukiedev.gitbook.io/wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ryukiedev.gitbook.io/wiki/shu-ju-jie-gou-yu-suan-fa/jian-zhi-offerswift/31.-zhan-de-ya-ru-dan-chu-xu-lie.md).

# 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 题相同：<https://leetcode-cn.com/problems/validate-stack-sequences/>

  来源：力扣（LeetCode）

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

  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 二、 分析

本题一上来难以找到思路。对于这样的问题，举例子找规律是比较合适的。这样在面试的时候面试官也更能理解我们的思路，而不是上来直接把答案 `默写` 出来。

解决这个问题很直观的想法就是建立一个辅助栈，把输入的第一个序列中的元素依次压入，并按照第二个序列的顺序依次冲该栈中弹出元素。

### 2.1 举例分析

#### 输入一：pushed = \[1,2,3,4,5], popped = \[4,5,3,2,1]

|  步骤 |  操作 |   栈  | 弹出数字 |
| :-: | :-: | :--: | :--: |
|  1  | 压入1 |   1  |      |
|  2  | 压入2 |  12  |      |
|  3  | 压入3 |  123 |      |
|  4  | 压入4 | 1234 |      |
|  5  | 弹出4 |  123 |   4  |
|  6  | 压入5 | 1235 |      |
|  7  | 弹出5 |  123 |   5  |
|  8  | 弹出3 |  12  |   3  |
|  9  | 弹出2 |   1  |   2  |
|  10 | 弹出1 |      |   1  |

#### 输入二：pushed = \[1,2,3,4,5], popped = \[4,3,5,1,2]

|           步骤           |  操作 |   栈  | 弹出数字 |
| :--------------------: | :-: | :--: | :--: |
|            1           | 压入1 |   1  |      |
|            2           | 压入2 |  12  |      |
|            3           | 压入3 |  123 |      |
|            4           | 压入4 | 1234 |      |
|            5           | 弹出4 |  123 |   4  |
|            6           | 弹出3 |  12  |   3  |
|            7           | 压入5 |  125 |      |
|            8           | 弹出5 |  12  |   5  |
| 尝试弹出下一个1，但是栈顶元素为2，无法弹出 |     |      |      |

#### 规律总结

从这里我们发现了如下规律：

* 栈顶元素如果等于下一个弹出元素：可以弹出
* 栈顶元素不等于下一个弹出元素：可以压入下一个待压入的元素
  * 直到将下一个需要弹出的元素入栈
* 如果所有元素都入栈后，没有下一个能弹出的元素，那么就不是一个弹出序列

## 三、 编码

```swift
func validateStackSequences(_ pushed: [Int], _ popped: [Int]) -> Bool {
    if pushed.isEmpty {
        return true
    }

    var result: [Int] = [], pA = 0, pB = 0

    while pB < popped.count {
        let b = popped[pB]

        // 栈顶元素如果等于下一个弹出元素：可以弹出
        if let top = result.last, top == b {
            result.removeLast()
            pB += 1
        }
        // 栈顶元素不等于下一个弹出元素：可以压入下一个待压入的元素
        else if pA < pushed.count {
            let a = pushed[pA]
            result.append(a)
            pA += 1
        }
        // 如果所有元素都入栈后，没有下一个能弹出的元素，那么就不是一个弹出序列
        else {
            return false
        }
    }

    return result.isEmpty
}
```

![LeetCode](/files/-Mi1UzEDWjsMwjhG5gTU)

## 四、 本题考点

* 考察分析复杂问题的能力。刚听到这个题的时候很多人可能都没有思路。这时候可以通过举一两个例子，一步步分析压栈、弹出的过程，进而寻找规律
* 考察对栈的理解