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，无法弹出

规律总结

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

• 栈顶元素如果等于下一个弹出元素：可以弹出

• 栈顶元素不等于下一个弹出元素：可以压入下一个待压入的元素

  • 直到将下一个需要弹出的元素入栈

• 如果所有元素都入栈后，没有下一个能弹出的元素，那么就不是一个弹出序列

三、 编码

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

四、 本题考点

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

• 考察对栈的理解