栈的压入弹出序列判断算法详解

问题描述

给定两个整数序列：

• pushV：压栈序列
• popV：待验证的弹栈序列

需要判断 popV 是否可能是 pushV 对应的弹栈序列。

核心思路

要解决这个问题，关键在于理解栈的后进先出特性。我们可以通过模拟整个压栈弹栈过程来验证序列的合法性。

具体规则如下：

• 压栈操作：元素按照 pushV 的顺序依次入栈
• 弹栈操作：在任意时刻，只能弹出栈顶元素
• 时机选择：可以在压入任意元素后选择弹出栈顶元素

关键洞察是：每当栈顶元素与当前期望弹出的元素匹配时，就立即弹出。这是一种贪心策略，因为如果此时不弹出，后续再想弹出这个元素就必须先把新压入的元素弹出来，这往往会导致顺序错乱。

完整代码实现

#include <vector>
#include <stack>

using namespace std;

class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // 使用辅助栈模拟压栈弹栈过程
        stack<int> st;
        // 双指针：_push 指向当前要压入的元素，_pop 指向当前要弹出的元素
        size_t _push = 0; // 压栈序列的索引
        size_t _pop = 0;  // 弹栈序列的索引

        // 遍历所有需要压入的元素
        while (_push < pushV.size()) {
            // 将当前元素压入栈中
            st.push(pushV[_push++]);
            
            // 检查栈顶元素是否与当前期望弹出的元素匹配
            // 如果匹配，则连续弹出所有匹配的元素
            while (!st.empty() && st.top() == popV[_pop]) {
                _pop++; // 移动弹栈序列指针
                st.pop(); // 弹出栈顶元素
            }
        }

        // 如果所有元素都能正确弹出，栈应该为空
        return st.empty();
    }
};

算法步骤详解

让我们通过一个具体例子来理解算法的执行过程：

示例输入：

• pushV = [1, 2, 3, 4, 5]
• popV = [4, 5, 3, 2, 1]

执行流程演示

初始状态下，辅助栈为空，指针 _push 指向 1，_pop 指向 4。

1. 压入阶段：依次将 1、2、3 压入栈中。此时栈内为 [1, 2, 3]，栈顶 3 不等于期望值 4，继续压入。
2. 匹配弹出：压入 4 后，栈顶变为 4，与期望值匹配。执行弹出操作，栈变为 [1, 2, 3]，_pop 指针移向 5。
3. 连续弹出：接着压入 5，栈顶为 5，匹配期望值 5，弹出。随后栈顶变为 3，匹配期望值 3，弹出。依此类推，直到栈内元素全部按序弹出。

最终栈为空，说明序列合法，返回 true。

复杂度分析

时间复杂度

主循环遍历 pushV 中的每个元素一次。内层循环虽然嵌套，但每个元素最多被压入和弹出各一次。因此总时间复杂度为 O(n)，其中 n 为序列长度。

空间复杂度

需要一个辅助栈来存储元素，最坏情况下需要存储所有 n 个元素。总空间复杂度为 O(n)。

边界情况处理

在实际编码中，需要注意以下边界条件：

1. 长度不一致：如果两个序列长度不同，直接返回 false。
2. 空序列：如果两个序列都为空，视为匹配，返回 true。
3. 单元素序列：需确保唯一元素匹配成功。

总结

这道题的核心在于利用辅助栈模拟实际过程，并结合双指针技巧跟踪进度。这种模拟法不仅适用于栈的相关问题，在很多其他算法场景中也有广泛应用。掌握这种思维方式，对于提升算法设计能力具有重要意义。

---

参考资料：

• LeetCode 946. 验证栈序列
• 数据结构与算法 - 栈的应用