【数据结构专题】剑指 Offer 31. 栈的压入、弹出序列-跟着帅地玩副业，开拓第二曲线PlayOffer

sincere 普通 2023年10月15日下午10:52

思路：借助辅助栈，在每次压入时和弹出序列比对，相同且栈不为空则弹出，最后判断栈是否为空
复杂度：时间复杂度O(N)，空间复杂度O(N)

class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        Stack<Integer> stack = new Stack<>();
        int i=0;
        for (int num : putIn) {
            stack.push(num);
            while (!stack.isEmpty()&& stack.peek()==takeOut[i]){
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}

0 赞同 0 条回复

谁仁普通 2023年9月6日下午4:34

bool validateStackSequences(int pushed[],int poped[],int n)
{
int stack[5];
int top = -1;
int pushIndex = 0;

for(int i=0,i<n;i++)
{
    //入栈
    stack[++top] = pushed[i];

    //检查栈顶元素
    while(top != -1&& stack[top] == poped[pushIndex])
    {
        top --;
        pushIndex++;
    }
}
return (top==-1);

}

void printStackSquence(int pushed[],int poped[],int n)//打印栈，弹出序列
{
print(“in stack: “);
for(int i = 0;i < n;i++)
{
printf(“%d “,pushed[i]);
}
printf(“\n”);
printf(” out stack “);
for(int i = 0;i < n;i++)
{
printf(“%d “,poped[i]);
}
printf(“\n”);

bool isVaild = validateStackSequences(pushed , poped,n);
if(isVaild)
{   
    printf(" is vailed queue" \n");
}
else
{
    printf(" is invailed queue" \n");
}

}//时间复杂度O（n），空间复杂度O（n);

0 赞同 0 条回复

QQiing 普通 2023年9月4日下午9:48

class Solution {
public:
bool validateStackSequences(vector& pushed, vector& popped) {

    if(pushed.size() <= 0)
    {
        return true;
    }
    stack<int> s;
    int k = 0;
    for(int i = 0; i < pushed.size(); i++)
    {
        s.push(pushed[i]);
        while(!s.empty() && s.top() == popped[k])
        {
            s.pop();
            k++;
        }
    }
    return s.empty();
}

};
时间复杂度：O(n^2)，空间复杂度：O(n)

0 赞同 0 条回复

羊毛同学普通 2023年8月29日下午9:34

打卡

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.size() == 0)
            return true;
        stack<int> s;
        int k = 0;
        for(int i = 0; i < pushed.size(); i++){
            s.push(pushed[i]);
            //如果poped数组元素和栈顶元素相同 那就一直出栈
            while(!s.empty() && popped[k] == s.top()){
                s.pop();
                k++;
            }
        }
        return s.empty();//如果栈空 表示弹出序列没问题
    }
};

0 赞同 0 条回复

我一定要坚持打卡普通 2023年8月27日下午9:57

思路

解题思路

拿到题目的时候，没有思路改怎么去处理；

使用栈去模拟入栈和出栈序列来进行判定

按照入栈序列和出栈序列进行的话，【如果出栈序列是正确的】最后栈中的一定是没有元素的【入栈和出栈结果确定且正确的话，只能有一种操作方式可以实现这种序列】，所以使用一个栈来进行模拟这个过程

遍历入栈序列，逐个将入栈序列插入栈中的同时，挨个比较出栈的值，如果出栈的值等于栈顶的元素，则表明在出栈序列执行完成之后，这个值是要出栈的，所以直接出栈该值然后在进行比较下一个出栈序列值，直至栈为空或者两个序列遍历完毕

解题方法

解题方法

// 这个题目使用一个栈来先进行模拟入栈，使用入栈的序列进行入栈操作
// 同时将入栈的元素与出栈序列的第i个值进行比较，如果相等的话，则模拟出栈操作

// 直至出栈操作结束或者入栈序列为空时候，进行判定，如果两个栈都为空的话，

// 说明出栈序列是对的，否则是错误的出栈序列

复杂度

时间复杂度:

时间复杂度： $O(n$)

空间复杂度:

空间复杂度： $O(n)$

Code

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        // 这个题目 使用一个栈来先进行模拟入栈，使用入栈的序列进行入栈操作
        // 同时将入栈的元素与出栈序列的第i个值进行比较，如果相等的话，则模拟出栈操作
        // 直至出栈操作结束或者入栈序列为空时候，进行判定，如果两个栈都为空的话，
        // 说明出栈序列是对的，否则是错误的出栈序列

        if(pushed==null|| popped.length<=0){
            return true;
        }
        Stack<Integer> stack = new Stack<>();
        int j=0;
        for(int i =0; i<pushed.length; i++){
            stack.push(pushed[i]);//将数据压入到栈中
            while(!stack.isEmpty()&&stack.peek()==popped[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();

    }
}

在使用for 循环和 while循环的时候，先逐个遍历入栈序列，在入栈的同时，用while循环比较出栈值与栈顶元素，若相等则模拟出栈操作，直至两个序列遍历完毕，最后验证栈为空

while(!stack.isEmpty()&&stack.peek()==popped[j]) 
    // 这个while  序列需要注意，使用的是短路&&，因为要先保证调用栈的peek()函数的时候，栈不能为空，否则会报错，所以要先保证栈内有数据，然后在进行比较
    // 栈为空的时候 可能第一个插入的数据是2 然后在出栈序列里边第一个序列也是2  然后就把2 弹出了，然后在while循环的时候，栈空了，就会报错，所以要判读

    // 另外是比较栈顶的元素 而不是只比较 新插入的元素pushed[i] 自己一开始编码的时候就弄错了 如果这样写的话会导致 栈内之前插入的数据被忽略

0 赞同 0 条回复

Di questa storia sempre a lie to 普通 2023年8月27日下午7:18

class Solution {
public:
bool validateStackSequences(vector& pushed, vector& popped) {
stack st;
int n = poped.size();
for(int i=0, j=0; i<n; i++){
st.emplace(pushed[i]);
while(!st.empty()&&st.top() popped[j]){
st.pop();
j++;
}
}
return st.empty();
}
};
时间复杂度：o(n)
空间复杂度：o(n)

0 赞同 0 条回复

Miracle· 普通 2023年8月24日下午8:47

事件复杂度o(n),空间复杂度o(n);
class Solution {
public:
bool validateStackSequences(vector& pushed, vector& popped) {
stack s;
int n = pushed.size();
for (int i = 0, j = 0; i < n; ++i) {
s.emplace(pushed[i]);
while (!s.empty() && s.top() popped[j]) {
s.pop();
j++;
}
}
return s.empty();
}
};

0 赞同 0 条回复

mpweixin用户普通 2023年8月24日下午7:30

//时间复杂度为o(n)
//空间复杂度为o(n)

class Solution {
public:
bool validateStackSequences(vector& pushed, vector& popped) {
stack ans_stack;
int count=pushed.size();

    for(int i=0,j=0;i<count;i++){
        ans_stack.push(pushed[i]);
        while(!ans_stack.empty() && ans_stack.top()==popped[j]){
            ans_stack.pop();
            j++;

        }
    }

    return ans_stack.empty();
}

};

0 赞同 0 条回复

sc_Yang 普通 2023年8月24日上午12:46

// 创建一个栈进行遍历模拟一遍入栈出栈顺序，同一组入栈栈出栈唯一对应一种顺序
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int n = pushed.size();
        for(int i=0, j=0; i<n; i++){
            st.push(pushed[i]);
            while(!st.empty()&& st.top()==popped[j]){
                st.pop();
                j++;
            }
        }
        return st.empty();
    }
};

0 赞同 0 条回复

💮黧大王.exe 普通 2023年8月21日下午4:00

时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public:
bool validateStackSequences(vector& pushed, vector& popped) {
stack stack1;
for(int i=0,j=0;i<pushed.size();i++){
stack1.push(pushed[i]);
while((!stack1.empty())&&stack1.top()popped[j]){
stack1.pop();
j++;
}
}
return stack1.empty();
}
};

0 赞同 0 条回复

辰北、普通 2023年8月20日下午5:15

//先反转再比值，for top cong0——》1，while里再-1；就变回了0；加一减一相等的话，证明；
bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize){
int stack= (int )malloc(sizeof(int )*pushedSize);
int top=0;
for(int i=0,j=0;i<pushedSize;i++){
stack[top++]=pushed[i];//先复制push到stack里/首先是比s1和pop0；成功则j+1,到poped1；
while(top>0&&stack[top-1]popped[j]){
top–;
j++;
}

}
free(stack);
return top0;
}

0 赞同 0 条回复

天亮说晚安普通 2023年8月20日上午9:58

学习了
时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<>();
        int n = pushed.length;
        for(int i=0,j=0;i<n;i++){
            stack.push(pushed[i]);
            while(!stack.isEmpty() && stack.peek()==popped[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}

0 赞同 0 条回复

Marc 普通 2023年8月19日下午11:34

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        stack = []
        j = 0 
        for i in pushed:
            stack.append(i)   
            while stack and stack[-1] == popped[j]:
                stack.pop()
                j += 1 
        return not stack

模拟就好了，O(N)

0 赞同 0 条回复

Sheng 永久会员 2023年8月19日下午6:36

代码写的复杂了，记录下，顺带贴上修改之后的
”’java
//判断栈的出栈序列是否合法
Stack stack = new Stack();

    int i = 0;
    int j = 0;
    while(i<pushed.size() && j<poped.size()) {
        while(i<pushed.size() && pushed[i] != poped[j])
        {
            stack.push(pushed[i]);
            i++;
        }
        while(stack.peek() == poped[j]) {
            stack.pop();
            j++;
        }
    }
    return stack.empty();

修改之后的
//上述代码逻辑重复了，简化一下
if(pushed null || pushed.length <= 0) {
return true;
}
int j = 0;
Stack stack = new Stack();
for(int m=0; m<pushed.size(); m++) {
stack.push(pushed[m]);
while(!stack.isEmpty() && stack.peek() poped[j]) {
stack.pop();
j++;
}
}
return stack.empty();

0 赞同 0 条回复

木子有点甜🍒 普通 2023年8月18日下午9:56

“`python
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
#pushed没有记录入栈的顺序，但是popped记录了出栈的顺序，对于每一个入栈的元素，通过跟pushed序列比较，可以知道它在对应的位置是否有出栈，如果这个位置没有出栈，那说明下一个动作是下一个元素入栈。因此用一个辅助栈记录入栈动作，每次按照pushed的顺序入栈一个元素，这个元素跟popped的出栈顺序比较，未出栈则继续入栈，继续找栈顶元素的出栈位置，找到后并出栈。
stack = []
i = 0

    for num in pushed:
        stack.append(num)
        while stack and stack[-1] == popped[i]:
            stack.pop()
            i += 1

    return not stack

“`python

0 赞同 0 条回复

Jou Siankwa 普通 2023年8月18日下午9:48

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int count = 0;
        for (int i : pushed) {
            stack.push(i);
            while (!stack.isEmpty() && stack.peek() == popped[count]){
                stack.pop();
                count++;
            }
        }
        if(stack.isEmpty()){
            return true;
        }else {
            return false;
        }
    }

    public static void main(String[] args) {
        int[] pushed = new int[]{1,2,3,4,5}, popped = new int[]{4,5,3,2,1};
        Solution sol = new Solution();
        boolean b = sol.validateStackSequences(pushed, popped);
        System.out.println(b);
    }
}

压入栈是判断栈顶元素是否是弹出的元素，如果是就一直弹出，直到栈顶元素不再是弹出元素序列中的值，最后压栈完毕，判断栈是否全部弹出，如果是说明符合。

0 赞同 0 条回复

一个人的风海吹了两遍普通 2023年8月18日下午4:38

这个有意思
以前学数据结构常考的点

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int j=0;
        for(int i=0; i< pushed.length; i++){
            stack.push(pushed[i]);
            while(!stack.isEmpty() && stack.peek()==popped[j]){
                j++;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

0 赞同 0 条回复

木木普通 2023年8月17日下午9:53

時間複雜度 : O(n) 空間複雜度: O(n)
利用一個輔助的stack來壓入pushed中的元素, 並在壓入元素後, 透過stack頂部元素與popped中的元素比較
如果相同則彈出stack頂部元素, 否則就繼續壓入剩餘元素, 最後如果是合法的popped 則stack應該為空.


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

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月17日下午9:15

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> stk;
        int size = pushed.size();
        for(int i = 0, j = 0; i<size; i++){
            stk.push(pushed[i]);
            while(!stk.empty() && stk.top() == popped[j]){
                stk.pop();
                j++;
            }
        }
        return stk.empty();
    }
};
时间o(n) 空间o(n)

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月17日下午3:54

使用一个辅助栈

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed == null || pushed.length <=0) {
            return true;
        }
        Stack<Integer> stack = new Stack();
        int k = 0;
        for(int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() == popped[k]) {
                stack.pop();
                k++;
            }
        }
        return stack.isEmpty();
    }
}

0 赞同 0 条回复

hhhhh 普通 2023年8月17日下午2:57

直接用一个栈压入pushed数组，然后逐个比较popped数组元素，最后看栈是否为空

“`cpp
class Solution {
public:
stack st;
bool validateStackSequences(vector& pushed, vector& popped) {
int i = 0;
int j = 0;
int in = pushed.size();
int jn = popped.size();
while(i < in){ st.push(pushed[i++]); while(j < jn && !st.empty() && st.top() == popped[j]){ st.pop(); j++; } } return st.empty(); } };

0 赞同 0 条回复

逸兴遄飞普通 2023年8月17日上午9:51

空间复杂度: O(1);
时间复杂度: O(N);

class Solution {
    // 双指针法，借助pushed数组本身作为栈进行模拟
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        // top设置为栈顶位置。
        // toDiscover指针记录pushed数组中还没有被遍历过元素的起始位置。
        int top = -1, toDiscover = 0;
        // 遍历并依次获取popped数组的全部元素，记为x
        for(int x: popped) {
            // 判断栈是否为空、栈顶元素是否与x相同，true则直接进行出栈操作
            if(top != -1 && pushed[top] == x) {
                top--;
                continue;
            }
            // 进行遍历操作，并将新遍历到的元素压入栈顶
            while(toDiscover < pushed.length && pushed[toDiscover] != x) {
                top++;
                pushed[top] = pushed[toDiscover];
                toDiscover++;
            }
            // 此时说明遍历完毕没有找到能够出栈的元素，序列错误返回false
            if(toDiscover == pushed.length) return false;
            toDiscover++;
        }
        return true;
    }
}

1 赞同 0 条回复

行动派小彩笔普通 2023年8月16日下午9:28

// 利用栈模拟栈入栈出的情况
// 时间遍历了数组O(n)，空间辅助栈O(n)
class Solution {
public:
    stack<int> stk;
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.size()==0) return true;
        int k = 0;
        for(int i=0;i<pushed.size();++i)
        {
            stk.push(pushed[i]);
            while(!stk.empty()&&stk.top()==popped[k])
            {
                stk.pop();
                k++;
            }
        }
        return stk.empty();// ? 为什么用k判断不行
    }
};

0 赞同 0 条回复

JustRtn 普通 2023年8月16日下午5:45

// 使用栈模拟压栈出栈, O(n)
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        std::stack<int> stk;
        for (size_t i = 0, j = 0; i < pushed.size(); i++) {
            stk.push(pushed[i]);
            while (!stk.empty() && stk.top() == popped[j]) {
                stk.pop();
                j++;
            }
        }
        return stk.empty();
    }
};

0 赞同 0 条回复

别扒拉我普通 2023年8月16日下午4:09

1、辅助栈。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed.length != popped.length){
            return false;
        }
        if(pushed.length == 0 && popped.length == 0){
            return true;
        }
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        int len = pushed.length;
        for(int i=0; i<len; i++){
            while(j<len && (stack.isEmpty() || stack.peek() != popped[i])){
                stack.push(pushed[j]);
                j++;
            }
            if(stack.peek() == popped[i]){
                stack.pop();
            }else{
                return false;
            }
        }
        return true;
    }
}

0 赞同 0 条回复

c 普通 2023年8月16日下午3:50

时间O(n),空间O(n)

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int i = 0; i < pushed.length; i++) {
            if (pushed[i]!=popped[j]){
                stack.push(pushed[i]);
            }else {
                j++;
                while (j< pushed.length && !stack.isEmpty()){
                    if(popped[j]==stack.peek()){
                        j++;
                        stack.pop();
                    }else {
                        break;
                    }
                }
            }
        }
        if (stack.isEmpty()){
            return true;
        }
        return false;
    }
}

0 赞同 0 条回复

【数据结构专题】剑指 Offer 31. 栈的压入、弹出序列

共以下 26 个回答

思路

解题方法

复杂度

时间复杂度:

空间复杂度:

Code

# 回答此问题取消回复

【数据结构专题】剑指 Offer 31. 栈的压入、弹出序列

共以下 26 个回答

思路

解题方法

复杂度

时间复杂度:

空间复杂度:

Code

# 回答此问题 取消回复

# 回答此问题取消回复