LC946. 验证栈序列
考研经常考手动模拟,练习一下代码加深印象
题目链接
就是当发现 比自己先入栈的元素,没有按照逆序输出的时候,一定不是合法的输出序列
比如说
入{3, 5, 7, 2, 1, 9, 12};
出 {7, 5, 3, 1, 12, 2, 9};
入栈序列是3 5 7 2 1 9 12
如果我们做408的选择题的话
就是按照这个规律去看
比如说7先出栈,那么他前面的3 5 一定是 5… 3 ,验证✅
{5,3,1,12,2,9}
5出栈,3一定在5后面 ✅
{3,1,12,2,9}
3 出栈
{1,12,2,9}
1 出栈,2一定在1后面出
{12,2,9}
12 出栈, 他前面的2和9还没出栈,那么一定是按照9…2的顺序
{2,9}
发现此时实际应该出栈的是stk.top()是9,但是目前popped[j]是2
那么这个时候popped序列指针就不会往后移动了,stk也不会继续pop
感觉还是官方的return stk.empty()比我这里简洁,我这里检查top元素其实是没必要的,因为前面while循环那里已经验证过了
class Solution
{
public:bool validateStackSequences(vector<int> &pushed, vector<int> &popped){stack<int> stk; // 定义一个栈int j = 0; // popped 序列的指针for (int i = 0; i < pushed.size(); i++){stk.push(pushed[i]); // 将 pushed 序列的元素依次压入栈中// 检查栈顶元素是否与 popped 序列的当前元素相同while (!stk.empty() && stk.top() == popped[j]){stk.pop(); // 弹出栈顶元素j++; // 移动 popped 序列的指针}}if (!stk.empty() && stk.top() != popped[j]) {return false;}return true; // 如果所有元素都符合规则,则序列是有效的}
};
方法二,模拟栈
class Solution
{
public:bool validateStackSequences(vector<int> &pushed, vector<int> &popped){int i = 0, j = 0;for (int k = 0; k < pushed.size(); k++){pushed[i] = pushed[k];i++;// 上面两句的意思是,将pushed[k]放入栈中,然后i++,表示栈顶指针向上移动// 其实就是把pushed自己当成一个栈,然后我们要控制i指向栈顶,j指向popped的元素while (i > 0 && pushed[i - 1] == popped[j]){i--; // 弹出栈顶元素,i指针向下移动,新的栈顶元素是pushed[i-1]j++; // 当前这个是满足条件的,继续验证下一个}}// 如果前面的while循环都能正常执行完,说明栈中的元素是按照popped的顺序弹出的// 如果出现了某次循环的时候,pushed[i-1] != popped[j],说明这个序列不是合法的// 也就是栈顶元素不等于popped[j],说明这个序列不是合法的// 所以说,如果i == 0,说明栈中的元素都被弹出了,说明这个序列是合法的return i == 0;}
};
可完整运行代码
#include <iostream>
#include <vector>
#include <stack>
using namespace std;class Solution
{
public:bool validateStackSequences(vector<int> &pushed, vector<int> &popped){stack<int> stk; // 定义一个栈int j = 0; // popped 序列的指针for (int i = 0; i < pushed.size(); i++){stk.push(pushed[i]); // 将 pushed 序列的元素依次压入栈中// 检查栈顶元素是否与 popped 序列的当前元素相同while (!stk.empty() && stk.top() == popped[j]){stk.pop(); // 弹出栈顶元素j++; // 移动 popped 序列的指针}}// 检查剩余的栈中元素是否符合逆序出栈的规则if (!stk.empty() && stk.top() != popped[j]) {return false;}return true; // 如果所有元素都符合规则,则序列是有效的}
};
// 示例使用
int main()
{Solution s;int pushed_arr[] = {3, 5, 7, 2, 1, 9, 12};int popped_arr[] = {7, 5, 3, 1, 2, 12, 9};vector<int> pushed(pushed_arr, pushed_arr + sizeof(pushed_arr) / sizeof(int));vector<int> popped(popped_arr, popped_arr + sizeof(popped_arr) / sizeof(int));cout << s.validateStackSequences(pushed, popped) << endl; // 输出: 1 (true)int pushed2_arr[] = {3, 5, 7, 2, 1, 9, 12};int popped2_arr[] = {7, 5, 3, 1, 12, 2, 9};vector<int> pushed2(pushed2_arr, pushed2_arr + sizeof(pushed2_arr) / sizeof(int));vector<int> popped2(popped2_arr, popped2_arr + sizeof(popped2_arr) / sizeof(int));cout << s.validateStackSequences(pushed2, popped2) << endl; // 输出: 0 (false)return 0;
}
我感觉和栈的括号匹配是一样的
有几种数字 就有几种括号