【牛客JZ31】—栈的压入弹出序列判断算法详解

坚持用 清晰易懂的图解 + 代码语言，让每个知识点变得简单！
🚀呆头个人主页详情
🌱 呆头个人Gitee代码仓库
📌 呆头详细专栏系列
座右铭： “不患无位，患所以立。”

---

---

摘要

---

目录

题目描述

牛客链接直达----------请点击

给定两个整数序列：

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

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

---

核心思路

要解决这个问题，我们需要理解栈的工作机制：

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

关键洞察：我们可以通过模拟整个压栈弹栈过程来验证序列的合法性。

完整代码实现

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

执行过程模拟

// 初始状态
stack<int> st;        // 空栈
size_t _push = 0;     // 指向元素1
size_t _pop = 0;      // 指向元素4

第1轮循环：

// 压入元素1
st.push(1);           // 栈：[1]
_push = 1;            // 指向元素2// 检查栈顶：1 != 4，不匹配，继续

第2轮循环：

// 压入元素2
st.push(2);           // 栈：[1, 2]
_push = 2;            // 指向元素3// 检查栈顶：2 != 4，不匹配，继续

第3轮循环：

// 压入元素3
st.push(3);           // 栈：[1, 2, 3]
_push = 3;            // 指向元素4// 检查栈顶：3 != 4，不匹配，继续

第4轮循环：

// 压入元素4
st.push(4);           // 栈：[1, 2, 3, 4]
_push = 4;            // 指向元素5// 检查栈顶：4 == 4，匹配！
st.pop();             // 栈：[1, 2, 3]
_pop = 1;             // 指向元素5

第5轮循环：

// 压入元素5
st.push(5);           // 栈：[1, 2, 3, 5]
_push = 5;            // 超出范围// 检查栈顶：5 == 5，匹配！
st.pop();             // 栈：[1, 2, 3]
_pop = 2;             // 指向元素3// 继续检查：3 == 3，匹配！
st.pop();             // 栈：[1, 2]
_pop = 3;             // 指向元素2// 继续检查：2 == 2，匹配！
st.pop();             // 栈：[1]
_pop = 4;             // 指向元素1// 继续检查：1 == 1，匹配！
st.pop();             // 栈：[]
_pop = 5;             // 超出范围

最终结果：栈为空，返回 true

---

算法复杂度分析

时间复杂度

// 主循环：遍历pushV中的每个元素
while(_push < pushV.size()) {  // O(n)st.push(pushV[_push++]);   // O(1)// 内层循环：每个元素最多被弹出一次while(!st.empty() && st.top() == popV[_pop]) {  // 总计O(n)_pop++;st.pop();}
}

• 外层循环：执行 n 次（n 为序列长度）
• 内层循环：虽然是嵌套循环，但每个元素最多被压入和弹出各一次
• 总时间复杂度：O(n)

---

空间复杂度

stack<int> st;  // 辅助栈，最坏情况下存储所有元素

• 辅助栈空间：最坏情况下需要存储所有 n 个元素
• 总空间复杂度：O(n)

---

边界情况处理

空序列处理

bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// 如果两个序列长度不同，直接返回falseif (pushV.size() != popV.size()) {return false;}// 空序列的情况if (pushV.empty()) {return true;  // 两个空序列匹配}// 原算法逻辑...
}

---

单元素序列

// 测试用例
vector<int> pushV = {1};
vector<int> popV = {1};
// 结果：truevector<int> pushV2 = {1};
vector<int> popV2 = {2};
// 结果：false

---

总结

通过这道题的分析，我们深入理解了以下几个重要概念：

1. 栈的模拟：通过辅助栈来模拟实际的压栈弹栈过程
2. 双指针技巧：使用两个指针分别跟踪压栈和弹栈的进度
3. 贪心策略：每当栈顶元素与期望弹出元素匹配时，立即弹出
4. 算法验证：通过最终栈是否为空来验证序列的合法性

这种模拟法不仅适用于栈的相关问题，在很多其他算法场景中也有广泛应用。掌握这种思维方式，对于提升算法设计能力具有重要意义。

---

参考链接

1. LeetCode 946. 验证栈序列
2. 牛客网 - 栈的压入、弹出序列
3. 数据结构与算法 - 栈的应用
4. C++ STL stack 容器详解
5. 算法导论 - 栈和队列

关键词标签

栈 数据结构 算法模拟 双指针 C++STL