解题思路用真实栈模拟整个过程题目最直观的解法就是“抄起一个真实的栈”把压入、弹出过程完整演一遍。如果能顺利按照给定的弹出序列走完就说明该序列是合法的否则就是非法的整个模拟过程可以概括为以下几个步骤定义一个辅助栈 s用来模拟压栈和弹栈使用两个下标 in 和 out分别遍历压入序列 pushV 和弹出序列 popV依次处理弹出序列的每一个元素 popV[out](1) 如果当前栈顶元素不是我们要弹出的 popV[out]或者栈为空就需要从 pushV 里不断压入数字直到栈顶等于 popV[out] 或者 pushV 已经全部压完(2) 如果 pushV 全部压完仍然找不到匹配的数字说明这个弹出序列是不可能实现的直接返回 false(3) 如果找到了匹配的数字就将该数字弹出栈模拟弹栈并继续处理下一个弹出元素 out如果所有弹出元素都能按规则匹配完毕则返回 true代码实现以下是完整的 C 实现每一处关键逻辑都配有详细注释可以直接复制阅读或运行调试classSolution{public:boolIsPopOrder(vectorintpushV,vectorintpopV){//先搞定最白痴的情况两个数组不相等就一定不会是相对应的压栈与弹出序列if(pushV.size()!popV.size()){returnfalse;}//定义两个下标分别用来遍历pushV数组和popV数组intin0;intout0;//用一个真实的栈来模拟实打实的实现压栈和弹出的情况stackints;//先以popV数组为标准去判断pushV是不是压栈序列用out去遍历popVout为下标故要小于sizewhile(outpopV.size()){//如果s是空或者栈顶元素与出栈的元素不相等就入栈while(s.empty()||popV[out]!s.top()){//当然入栈的时候也不能闭着眼入要看看是否存在越界的情况if(inpushV.size()){s.push(pushV[in]);}//越界了就意味着即使我把pushV数组里面的所有的元素都压入栈//也无法从栈顶找到一个和popV[out]相等的数故可直接返回falseelse{returnfalse;}}//跳出循环之后意味着在pushV数组里找到了和popV[out]相等的数//这时候就要去匹配下一个出栈元素并在栈s中模拟实现出栈操作即 s.pop();s.pop();out;}//当遍历完并且popV和pushV里面的每个元素都有这一一对应的出入栈关系即可返回真returntrue;}};示例解读假设压入序列为 [1, 2, 3, 4, 5]弹出序列为 [4, 5, 3, 2, 1]我们一起来走一遍过程栈空需要弹出 4。压入 1、2、3、4栈顶为 4匹配弹出 4栈变为 [1, 2, 3]弹出序列移向 5栈顶为 3不等于 5。继续压入 5栈顶变为 5匹配弹出 5栈变回 [1, 2, 3]弹出序列移向 3栈顶 3 匹配弹出栈 [1, 2]弹出序列移向 2栈顶 2 匹配弹出栈 [1]弹出序列移向 1栈顶 1 匹配弹出栈空。所有弹出序列处理完毕返回 true如果换一个弹出序列 [4, 3, 5, 1, 2]则当弹出 1 时栈顶为 2pushV 已空无法匹配返回 false复杂度分析时间复杂度O(N)整个过程里每个数字最多只会被压入栈一次总压栈次数等于数组长度 N弹出也是 N 次。所以总体操作次数最多就是 2N时间复杂度稳稳的 O(N)空间复杂度O(N)最坏情况下需要借助辅助栈存储全部元素小结这道题之所以经典是因为它要求我们用程序去“还原”一个动态过程这正是栈这种受限数据结构的核心思维