本文共 1181 字，大约阅读时间需要 3 分钟。

题目

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

思路

模拟，看到有描述特别好的，直接拿过来

按照 popped 中的顺序模拟一下出栈操作，如果符合则返回 true，否则返回 false。

使用一个栈 st 来模拟该操作。将 pushed 数组中的每个数依次入栈，同时判断这个数是不是 popped 数组中下一个要 pop 的值，如果是就把它 pop 出来。最后检查栈是否为空。

• 初始化栈 stack，j = 0；
• 遍历 pushed 中的元素 x；
  • 当 j < popped.size() 且栈顶元素等于 popped[j]：
    • 弹出栈顶元素；
    • j += 1；
• 如果栈为空，返回 True，否则返回 False。

代码

class Solution {public:    bool validateStackSequences(vector
   
    & pushed, vector
    
     & popped) {        if(pushed.size() <= 0){            return true;        }                stack
     
       st;        int j = 0;        for(int i = 0;i < pushed.size();i++){            st.push(pushed[i]);                while(st.empty() == false && j < popped.size() && popped[j]==st.top()){                st.pop();                j++;            }        }        return st.empty();     }};
     
    
   

转载地址：https://blog.csdn.net/hanmin822/article/details/105615072 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！