本文共 1123 字，大约阅读时间需要 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]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：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 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！