当前位置：首页 > news >正文

LC946. 验证栈序列

news 2024/10/31 14:03:51

考研经常考手动模拟，练习一下代码加深印象

题目链接

就是当发现比自己先入栈的元素，没有按照逆序输出的时候，一定不是合法的输出序列

比如说
入{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;
}