乌海市网站建设_网站建设公司_漏洞修复_seo优化

一、题目描述

二、算法原理

思路：使用栈结构来模式出栈和入栈

以 pushed = [1,2,3,4,5]，popped = [4,5,3,2,1] 为例。

运行流程如下：

压入 1 → 栈：[1]，栈顶≠4（popped[0]），不弹栈。

压入 2 → 栈：[1,2]，栈顶≠4，不弹栈。

压入 3 → 栈：[1,2,3]，栈顶≠4，不弹栈。

压入 4 → 栈：[1,2,3,4]，栈顶 = 4，执行弹栈→栈：[1,2,3]，cur=1。

压入 5 → 栈：[1,2,3,5]，栈顶 = 5（popped[1]），执行弹栈→栈：[1,2,3]，cur=2。

此时 for 循环结束，进入 while 循环持续弹栈： 栈顶 = 3（popped[2]）→ 弹栈，cur=3，栈：[1,2]。 栈顶 = 2（popped[3]）→ 弹栈，cur=4，栈：[1]。 栈顶 = 1（popped[4]）→ 弹栈，cur=5，栈：[]。

辅助栈为空，返回 true，序列合法。

三、代码实现

class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { vector<int> stack; int cur = 0; for(auto& e : pushed) { stack.push_back(e);//入栈 while(!stack.empty() && stack.back() == popped[cur])//判断栈顶元素是否和 poped 的一样 { stack.pop_back(); cur++; } } if(stack.empty()) return true; else return false; } };