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

946.验证栈序列

article 2025/3/11 6:08:33

题目

链接：leetcode链接
在这里插入图片描述

思路分析

我们知道一个栈的一种入栈顺序可能对应多种出栈顺序，让我们肉眼来判断一下，还是很容易判断出来是不是正确的出栈顺序，那么如何用代码来实现呢？

OK，先掏一个栈s出来再说

int i = 0;

先把pushed进一个栈s，然后比较s.top 与 popped[i]，
如果相等，就s.pop，同时++i；
++i后再与s.top继续比较，直到不相等跳出循环

如果不相等，就继续将pushed入栈

pushed走完了之后，去查看s是否为空，如果s为空，说明匹配上了，否则，不匹配。

在这里插入图片描述

代码

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> s;
        int i = 0;
        
        for(auto e:pushed)
        {
            s.push(e);
          
            while(!s.empty()&&s.top() == popped[i])
            {
                ++i;
                s.pop();
            }
           
        }

        return s.empty();
    }

查看全文

http://www.kler.cn/a/297685.html