# 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)

## 四、 本题考点

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET 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?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.