面试题31_栈的压入和弹出序列.md

面试题 31 ：栈的压入和弹出序列

---

leetcode-cn 题目地址

📗difficulty： Medium

🎯Tags：

• 栈

---

1. 题目描述📃

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {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/

---

2. 解题思路💡

反向模拟

下面的我第一次写这道题，自己的一个思考，大概耗时 20 分钟。

首先，将 popped 数组入栈，以备按顺序弹出，模拟栈的操作。

然后将 pushed 也模拟栈的操作，首先将元素按序列入栈。然后比较这 2 个栈的栈顶，如果相等，那么就弹出栈顶元素，这表明匹配了。然后，继续判断，直到 ①pushed为空 或者 ②栈顶元素不相等的情况。

当 pushed 数组遍历完成，开始处理剩余的栈中的元素。

• 如果栈顶元素相等，那么同时 2 个栈同时弹出栈顶元素。
• 如果栈顶元素不相等，那么仅仅弹出 popped 栈的栈顶元素。
• 如果 popped 已经空，处理完成，pushed 还没有空，说明不匹配；否则匹配成功。

注意：

Java 中建议使用 Deque 和 LinkedList 实现 Stack 的功能，而不是使用 Stack 类。

代码实现

public boolean validateStackSequences(int[] pushed, int[] popped) {
    Deque<Integer> pushedStack = new LinkedList<>();
    Deque<Integer> poppedStack = new LinkedList<>();
    for (int i = 0; i < popped.length; i++) {
        poppedStack.offerLast(popped[i]);
    }
    int idx = 0;
    // 题目给定了 pushed.length == popped.length
    while (idx < pushed.length) {
        pushedStack.offerFirst(pushed[idx]);
        idx++;
        while (!pushedStack.isEmpty() && pushedStack.peekFirst().equals(poppedStack.peekFirst())) {
            pushedStack.pollFirst();
            poppedStack.pollFirst();
        }
    }
    while (!poppedStack.isEmpty()) {
        if (poppedStack.peekFirst().equals(pushedStack.peekFirst())) {
            poppedStack.pollFirst();
            pushedStack.pollFirst();
        } else {
            poppedStack.pollFirst();
        }
    }
    return pushedStack.isEmpty();
}

复杂度分析

• 时间复杂度：O(n) 。
• 空间复杂度：O(2 n) 。需要 2 个辅助栈。

以下代码来自 leetcode-cn 用户 Krahets 的题解，感谢他的精彩讲解。

模拟代码的优化

优化的代码，只需要使用一个辅助栈，对于 popped 数组的处理使用一个指针即可。

代码实现

// 优化算法
public boolean validateStackSequences(int[] pushed, int[] popped) {
    Deque<Integer> stack = new LinkedList<>();
    int idx = 0;
    for (int num : pushed) {
        stack.offerFirst(num);
        while (!stack.isEmpty() && stack.peekFirst() == popped[idx]) {
            stack.pollFirst();
            idx++;
        }
    }
    return stack.isEmpty();
}

复杂度分析

• 时间复杂度：O(n) 。
• 空间复杂度：O(n) 。需要 1 个辅助栈 和 几个指针。

---

3. 总结🎯

相似题目

面试题30. 包含min函数的栈

虽然可以使用内建的类实现，但是面试官更加希望面试者自己手写一个栈。

可以选择使用数组实现，也可以选择 链表实现栈。

使用数组，需要考虑栈的扩容操作；使用链表的话，选择单链表，需要一点点的小技巧。

请在本题尝试使用 自己手写 的方法，完成 面试题 30。