【牛客JZ31】—栈的压入弹出序列判断算法详解
坚持用清晰易懂的图解+代码语言，让每个知识点变得简单！
🚀呆头个人主页详情
🌱 呆头个人Gitee代码仓库
📌 呆头详细专栏系列
座右铭：“不患无位，患所以立。”
【牛客JZ31】—栈的压入弹出序列判断算法详解
摘要
目录
题目描述
给定两个整数序列：
pushV：压栈序列popV：待验证的弹栈序列
需要判断 popV 是否可能是 pushV 对应的弹栈序列。
核心思路
要解决这个问题，我们需要理解栈的工作机制：压栈操作：元素按照 pushV 的顺序依次入栈弹栈操作：在任意时刻，只能弹出栈顶元素时机选择：可以在压入任意元素后选择弹出栈顶元素关键洞察：我们可以通过模拟整个压栈弹栈过程来验证序列的合法性。
完整代码实现
#include<vector>#include<stack>usingnamespace std;classSolution{public:boolIsPopOrder(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)
边界情况处理
空序列处理
boolIsPopOrder(vector<int>& pushV, vector<int>& popV){// 如果两个序列长度不同，直接返回falseif(pushV.size()!= popV.size()){returnfalse;}// 空序列的情况if(pushV.empty()){returntrue;// 两个空序列匹配}// 原算法逻辑...}单元素序列
// 测试用例 vector<int> pushV ={1}; vector<int> popV ={1};// 结果：true vector<int> pushV2 ={1}; vector<int> popV2 ={2};// 结果：false总结
通过这道题的分析，我们深入理解了以下几个重要概念：
- 栈的模拟：通过辅助栈来模拟实际的压栈弹栈过程
- 双指针技巧：使用两个指针分别跟踪压栈和弹栈的进度
- 贪心策略：每当栈顶元素与期望弹出元素匹配时，立即弹出
- 算法验证：通过最终栈是否为空来验证序列的合法性
这种模拟法不仅适用于栈的相关问题，在很多其他算法场景中也有广泛应用。掌握这种思维方式，对于提升算法设计能力具有重要意义。
参考链接
关键词标签
栈数据结构算法模拟双指针C++STL
