九号球普通 2023年11月8日下午8:12

“`java
使用栈
class Solution {
public boolean validateBookSequences(int[] putIn, int[] takeOut) {
Stack stack = new Stack();
int takeIndex = 0;
for (int i = 0; i< putIn.length; i++) { if (takeOut[takeIndex] != putIn[i]) { stack.push(putIn[i]); continue; } takeIndex++; while (!stack.isEmpty() && stack.peek() == takeOut[takeIndex]) { stack.pop(); takeIndex++; } } return stack.isEmpty(); } }

0 赞同 0 条回复

招舟子普通 2023年8月25日上午10:13

“` java
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack stack = new Stack<>();
int k = 0;
for(int i=0;i}

}
借助辅助栈实现

0 赞同 0 条回复

mpweixin用户普通 2023年7月21日下午11:37

时间：O(n)
空间：O(n)
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 条回复

橙子陈普通 2023年7月16日上午2:25

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();
    }
}

时间复杂度O(n)
空间复杂度O(n)

0 赞同 0 条回复

淡色花樱普通 2023年7月14日下午5:25

“`java
class Solution{
public boolean validateStackSequences(int [] pushed, int [] popped){
if(pushed == null || pushed.length<=0){ return true; } int k = 0; Stack stack = new Stack();辅助栈
for(int i = 0; i

0 赞同 0 条回复

Tang 普通 2023年7月9日下午3:24

class Solution {
    /**
        解题思路：模拟入栈出栈，如果模拟成功，则为true,否则为false
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0, j = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        if (stack.isEmpty()) {
            return true;
        }
        return false;
    }
}

时间复杂度：O(N) 空间复杂度：O(N)

0 赞同 0 条回复

憨憨永久会员 2023年7月5日下午6:13

通过一个栈来模拟出入栈，如果最后模拟栈空的话就是可用序列，否则就不可用

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

0 赞同 0 条回复

BOZ 普通 2023年7月4日下午5:17

【思路】定义一个栈，按pushed顺序push，如果碰到可以pop的就pop，最后push完之后如果pop不了了就失败，pop完了就成功
【时间复杂度】O(n)
【空间复杂度】O(n)

class Solution {
public:
    bool validateStackSequences(vector& pushed, vector& popped) {
        std::stack s;
        int popped_ptr = 0;

        for (auto &val: pushed) {
            s.push(val);
            // pop if match
            while (!s.empty() && s.top() == popped[popped_ptr]) {
                s.pop(); popped_ptr++;
            }
        }

        if (popped_ptr == pushed.size()) return true;
        else return false;
    }
};

0 赞同 0 条回复

3_🔥 永久会员 2023年7月4日下午3:19

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

0 赞同 0 条回复

Sexypig. 普通 2023年7月4日上午1:30

这是一道经典的栈的问题。我们可以使用一个辅助栈来模拟栈的压入和弹出操作。
具体步骤如下：
1. 初始化一个空栈和弹出序列的索引i。
2. 遍历压入序列，将元素依次压入栈中。
3. 每次压入元素后，判断栈顶元素是否与弹出序列的当前元素相等。如果相等，则将栈顶元素弹出，并将弹出序列的索引i加1。
4. 最后，如果栈为空且弹出序列的索引i等于弹出序列的长度，则说明弹出序列是压入序列的一个合法弹出序列；否则，不是合法弹出序列。
下面是具体的实现代码：

def validateStackSequences(pushed, popped):
    stack = []  # 辅助栈
    i = 0  # 弹出序列的索引
    for num in pushed:
        stack.append(num)  # 将元素压入栈中
        while stack and stack[-1] == popped[i]:  # 判断栈顶元素是否与弹出序列的当前元素相等
            stack.pop()  # 弹出栈顶元素
            i += 1  # 弹出序列的索引加1
    return len(stack) == 0 and i == len(popped)  # 判断栈是否为空且弹出序列的索引是否等于弹出序列的长度

时间复杂度分析：
– 遍历压入序列的时间复杂度为O(N)，其中N为序列的长度。
– 在每次压入元素后，可能需要弹出栈顶元素，因此弹出操作的时间复杂度为O(N)。
– 因此，总的时间复杂度为O(N)。
空间复杂度分析：
– 使用了一个辅助栈，最坏情况下，辅助栈的空间复杂度为O(N)。
– 因此，总的空间复杂度为O(N)。

0 赞同 0 条回复

大大普通 2023年7月1日下午9:54

C++:
法一：利用map 时间是法二的3倍(-o-)
class Solution {
public:
//前后看一看
//对于popped里面的数，都能在前面中对应一个坐标 map[数]=坐标
//map检验是否被标记过
 // 需要满足的条件：  //下标可以减小，必须顺次序  //下标也可以增大
    bool validateStackSequences(vector& pushed, vector& popped) {
       if(pushed.size()==0)return true;
      map p;
      map m;
         for(int i=0;ipopped[i+1]){
             for(int j=popped[i]-1;j>popped[i+1];j--)
                 if(m[j])return false;//没有顺次序减小
           }
             m[popped[i]]=0;             
             m[popped[i+1]]=0;
          }
           return true;      
    }
};

法二：利用栈
class Solution {
public://利用栈来解决 
    bool validateStackSequences(vector& pushed, vector& popped) {
      stack s;
      int j=0;
      for(int i=0;i

0 赞同 0 条回复

GGBond 普通 2023年7月1日下午1:17

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]);
            //出栈，出栈顺序需要和popped数组顺序一致
            while(!stack.isEmpty() && stack.peek() == popped[j]){
                stack.pop();
                j++;
            }
        }

        //如果栈为空，说明两个序列分别对应入栈，出栈顺序
        return stack.isEmpty();
    }


}

0 赞同 0 条回复

mpweixin用户普通 2023年7月1日下午12:45

java
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed == null && pushed.length <= 0) {
            return true;
        } 

        int i = 0, k = 0;
        //直接创建一个栈来模拟
        Stack<Integer> s = new Stack<>();
        for(; i < pushed.length; i ++ ) {
            s.push(pushed[i]);
            while(!s.isEmpty() && s.peek() == popped[k]) {
                s.pop();
                k++;
            }
        }
        return s.isEmpty();
        // if(s.isEmpty()) {
        //     return true;
        // }
        // return false;
    }
}

时间复杂度O(N), 空间复杂度O(N)

0 赞同 0 条回复

CV大神普通 2023年6月29日下午10:57

public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new LinkedList<>();
        int index = 0;
        for (int push : pushed) {
            //依次放入栈中
            stack.push(push);
            //每放入一个，就尝试取出，可能会连续取出
            while (!stack.isEmpty() && stack.peek() == popped[index]) {
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty();

    }

时间复杂度O(n)，控件复杂度O（n）

0 赞同 0 条回复

名字什么的好麻烦普通 2023年6月28日上午11:48

辅助栈

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

0 赞同 0 条回复

伏月三十普通 2023年6月27日下午7:20

时间复杂度是O(n) 空间复杂度是O(n)

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed==null || pushed.length==0){
            return true;
        }

        ArrayDeque<Integer> stack=new ArrayDeque<>();
        int k=0;
        for(int i=0;i<pushed.length;i++){
            stack.push(pushed[i]);
            while(!stack.isEmpty() && popped[k]==stack.peek()){
                stack.pop();
                k++;
            }
        }
        return stack.isEmpty();
    }
}

0 赞同 0 条回复

～普通 2023年6月26日下午8:56

class Solution {
public:
bool validateStackSequences(vector& pushed, vector& popped) {
if(pushed.size()!=popped.size()){
return false;
}
stack stack;
int push = 0;
int pop = 0;
while(push<pushed.size()){
stack.push(pushed[push]);
while(!stack.empty()&&stack.top()popped[pop]){
stack.pop();
pop++;
}
push++;
}
while(!stack.empty()&&stack.top()popped[pop]){
stack.pop();
pop++;
}
return stack.empty();
}
};
时间复杂度O（N），空间复杂度O（N）

0 赞同 0 条回复

Bello~ 普通 2023年6月26日上午9:51

时间复杂度O(N)
空间复杂度O(N)

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

0 赞同 0 条回复

WhyBeBubble 普通 2023年6月26日上午12:16

class Solution { // 实现
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        deque<int> stack;
        int next = 0;
        for (int i = 0; i < pushed.size(); ++i) {
            stack.push_back(pushed[i]);
            while(!stack.empty() && stack.back() == popped[next]) {
                stack.pop_back();
                next++;
            }
        }
        return stack.empty() ? true : false;
    }
};

0 赞同 0 条回复

残月冷骄阳普通 2023年6月25日下午11:13

Problem: 剑指 Offer 31. 栈的压入、弹出序列

复杂度

时间复杂度: $O(n)$
空间复杂度: $O(n)$

Code

class Solution {
      public   boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed.length != popped.length) {
            return false;
        }
        Stack<Integer> stack = new Stack();
        for (int i = 0, j = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() <span class="text-highlighted-inline" style="background-color: #fffd38;"> popped[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty() ? true : false;
    }
}

0 赞同 0 条回复

张君雅小妹妹普通 2023年6月25日下午11:01

时间复杂度：O(n)
额外空间复杂度：O(n)

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() && popped[k] == stack.peek()){
                stack.pop();
                k++;
            }
        }
        return stack.isEmpty();

    }
}

0 赞同 0 条回复

硬核洋葱普通 2023年6月25日下午10:13

class Solution {
public:
    stack<int> stk;

    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int psize = pushed.size();
        int popindex = 0;

        for(int i = 0; i < psize; ++i){
            stk.push(pushed[i]);
            while(!stk.empty() && stk.top() == popped[popindex]){
                stk.pop();
                ++popindex;
            }
        }

        return stk.empty();
    }
};

栈的弹入弹出，，做法就是模拟！！
入栈，看栈头是否是当前弹出序列位置上的数，是则出栈，循环判断。当栈为空或者栈头并非弹出序列对应数的时候，再重启入栈操作
最后如果栈为空则模拟成功
时间复杂度 O(n) 空间复杂度 O(n)

0 赞同 0 条回复

Dsjh 普通 2023年6月25日下午4:55

···cpp
// c++实现
class Solution {
public:
bool validateStackSequences(vector& pushed, vector& popped) {
stack s;
int j=0;
for(int i=0;i<pushed.size();i++){
s.push(pushed[i]);
// 注意判空
while(!s.empty() && s.top() popped[j]){
s.pop();
j++;
}
}
return s.empty();
}
};

0 赞同 0 条回复

普通 2023年6月25日下午2:26

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

循环压栈序列,遇到栈顶元素等于弹出序列的当前元素则执行出栈,循环结束栈中如果还有元素则说明无法按照弹出序列的顺序弹出

0 赞同 0 条回复

Tlhey 普通 2023年6月25日上午9:30

”’C
//学习的一个高分java题解的老哥写的，空间是O(1)的，不过本质上是循环使用了pushed数组
bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize){
int top=-1, p=0;
for(int i=0;i<poppedSize;i++){
int e=popped[i];
if(top>-1 && pushed[top]e){
top–;
continue;
}
while(p<pushedSize && pushed[p]!=e){
pushed[++top]=pushed[p++];
}
if(ppushedSize) return false;
p++;
}
return true;

}”’

0 赞同 0 条回复

怀瑾永久会员 2023年6月24日下午11:04

C++实现

#include <stack>
#include <vector>
using namespace std;

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
    stack<int> s;
    int n = pushed.size(), m = popped.size();
    int i = 0, j = 0;
    for (; i < n; ++i) {
        s.push(pushed[i]);
        while (!s.empty() && s.top() == popped[j]) {
            s.pop();
            ++j;
        }
    }
    return j == m;
}

0 赞同 0 条回复

彦，，# 普通 2023年6月24日下午9:53

嗯，，就先把题目弄懂吧，唉

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> stack1;
        int len = pushed.size();
        int j = 0;
        for(int i =0;i <len; i++)
        {
            stack1.push(pushed[i]);
            while(!stack1.empty() && stack1.top() == popped[j])
            {
                stack1.pop();
                j++;
            }
        }
        return stack1.empty();
    }

0 赞同 0 条回复

* 普通 2023年6月24日下午9:51

”’C++实现
class Solution {
public:
bool validateStackSequences(vector& pushed, vector& popped) {
int a=0,b=0;
stack s;
while(a<pushed.size()){
if(pushed[a]popped[b])
{
a++,b++;
}
else
{
if(!s.empty()&&s.top()popped[b])
{
s.pop(),b++;
}
else
{
s.push(pushed[a]),a++;
}
}
}
while(!s.empty())
{
if(s.top()!=popped[b])
{
return false;
}
s.pop(),b++;
}
return true;
}
};

0 赞同 0 条回复

张开怀普通 2023年6月24日下午8:41

class Solution{
public:
      bool validataStackSequences(vector& pushed, vector& popped){
            if(pushed.empty()){
                  return true;
            }
            int k=0;
            stack s;
            for (int i=0;i

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

0 赞同 0 条回复

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

“`py
辅助栈
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
lst = []
idx = 0
for x in pushed:
lst.append(x)
while lst and lst[-1] == popped[idx]:
lst.pop()
idx += 1
return not lst
““

0 赞同 0 条回复

花老爷普通 2023年6月24日下午6:24

模拟
时间：O(n)
空间：O(n)

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<>();
        // idx1表示pushed数组的索引，idx2表示popped数组的索引
        int idx1 = 0, idx2 = 0;
        while (idx2 < popped.length) {
            if (stack.isEmpty()) {
                stack.push(pushed[idx1]);
            // 当pushed数组全部都被推入stack中并且stack应该弹出的元素不是当前idx2指向元素，则不可能时压栈序列的弹出序列，直接返回false
            } else if (idx1 >= pushed.length && stack.peek() != popped[idx2]) {
                return false;
            // stack与popped匹配，弹出并且idx2向右移动
            } else if (stack.peek() == popped[idx2]) {
                stack.pop();
                idx2++;
            } else {
            // stack与popped不匹配，将idx1指向元素压入栈
                stack.push(pushed[idx1++]);
            }
        }
        // 一直成功模拟到尽头，直接返回true
        return true;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月24日下午3:46

C++
TC: O(n)
SC: O(n)

模拟就行，思路跟帅地题解一样

class Solution {
    /*
    [4 5]


<pre><code>假如在一个元素前入栈，在那个元素还没出栈的时候，你不能出栈

*/
</code></pre>

public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int>stk;
        int n = popped.size();
        int indexPop = 0;
        for (int val : pushed) {
            stk.push(val);
            if (stk.top() <span class="text-highlighted-inline" style="background-color: #fffd38;"> popped[indexPop]) {
                while (!stk.empty() && stk.top() </span> popped[indexPop]) {
                    stk.pop();
                    indexPop++;
                }
            }
        }
        return stk.size() <span class="text-highlighted-inline" style="background-color: #fffd38;"> 0 && indexPop </span> n;
    }
};

0 赞同 0 条回复

大鑫啊普通 2023年6月24日下午2:57

时空复杂度：O(n)
1、先判断入栈数组是否为空
2、建立辅助栈，循环将入栈元素压入栈中，同时从头开始将出栈数组与栈顶指针比较，若相同且栈内有数据，则栈出栈，并且出栈数组指针加1
3、到最后如果栈为空，则测试的出栈顺序成立

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed ==null || pushed.length <= 0){
            return true;
        }
        int k=0;
        Stack<Integer> stack = new Stack();
        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 条回复

断舍离永久会员 2023年6月24日下午2:37

class Solution {
    //时间复杂度O(n)、空间复杂度O(n)
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed == null || pushed.length == 0){
            return true;
        }
        Stack<Integer> stack = new Stack();
        for(int i = 0, k = 0; i < pushed.length; i++){
            //将push序列的值压入堆栈
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() == popped[k]){
                stack.pop();
                k++;
            }
        }

        //若最后辅助栈为空，说明入栈和出栈顺序一致
        return stack.isEmpty();
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月24日下午2:00

bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize){
   int*stack=(int*)malloc(sizeof(int)*pushedSize);
   int top=0;
   for(int i=0,k=0;i<pushedSize;i++)
   {
       stack[top++]=pushed[i];
       while(top>0&&stack[top-1]==popped[k])
       {
           top--;
           k++;
       }
   }
   free(stack);
   return top==0?true:false;
}

时间复杂度是O(n)
空间复杂度为O(n)

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月24日下午12:11

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        i, j = 0, 0
        stack = []

        for num in pushed:
            stack.append(num)
            i += 1
            # 与stack比较 而不是pushed
            while i > 0 and stack[i - 1] == popped[j]:
                j += 1
                i -= 1
                stack.pop()

        return not stack

0 赞同 0 条回复

局外人普通 2023年6月24日上午12:40

思想：模拟。采用一个栈，对两个序列设置双指针：对于压入序列元素分别压入，若栈顶与弹出序列当前元素一致，则弹出。遍历完压入序列后，若栈为空，则为合法序列，否则不合法。

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

0 赞同 0 条回复

江畅普通 2023年6月23日下午11:22

// 栈的压入弹出序列
// 时间复杂度 O(N)
// 空间复杂度 O(N)
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st; // 存储入栈元素

        for (int i = 0, j = 0; i < pushed.size(); ++i) {
            st.push(pushed[i]); // 模拟入栈

            // 出栈元素满足入栈顺序则将入栈元素弹出
            while (!st.empty() && st.top() == popped[j]) {
                st.pop();
                ++j;
            }
        }

        return st.empty();
    }
};

0 赞同 0 条回复

行动派小彩笔普通 2023年6月23日下午10:51

// 直接用栈来模拟  时间O(n ) ,空间O(n)
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]);
            while(!s.empty()&&s.top()==popped[k]) // 可能连续弹出
            {
                s.pop();
                ++k;
            }
        }
        return s.empty();

    }
};

// 时间O(n),空间O(1)，用数组模拟栈，但是改变了原本的数组
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {

        int i =0;
        int j = 0;
        for(auto num:pushed)
        {
            pushed[i] = num;
            while(i>=0&&pushed[i]==popped[j])
            {
                --i;
                ++j;
            }
            ++i;
        }
        return i==0; // 表示全部弹出

    }
};

1 赞同 0 条回复

mpweixin用户永久会员 2023年6月23日下午10:15

//修修改改写出来的
//思路：模拟压栈弹栈的过程，如果能顺利把popped数组遍历到底，说明成功匹配
public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack();
        int index = 0;

        for(int i = 0;i < pushed.length;i++){
            stack.push(pushed[i]);

            while(!stack.isEmpty() && popped[index] == stack.peek()){  //一边压栈，如果需要弹栈，就弹栈
                stack.pop();
                index++; //指向需要弹的元素
                if(index == popped.length){
                    return true;
                }
            }
        }


        if(stack.isEmpty() && index == popped.length){ //顺利弹完
            return true;
        }

        while(!stack.isEmpty()){    
            int top = stack.pop();  //一个一个弹出来匹配
            if(top == popped[index]){
                index++;
            }
        }

        //要是能成功匹配，index应该指向popped.length
        if(index == popped.length){ 
            return true;
        }else{
            return false;
        }
    }

0 赞同 0 条回复

Ming 普通 2023年6月23日下午10:11

“`java
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
//画图模拟
if(pushed == null || pushed.length <= 0) { return true; } int k = 0; Stack stack = new Stack();
for(int i = 0; i

0 赞同 0 条回复

yxy 普通 2023年6月23日下午7:48

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

简单

0 赞同 0 条回复

mpweixin用户普通 2023年6月23日下午7:23

思路：
入栈元素每入栈一个就与popped序列中的元素做比较，如果相等，出栈，popped序列的指针加一，最后栈为空则二者相符，否则不相符
代码c++
”’
class Solution {
public:
bool validateStackSequences(vector& pushed, vector& popped) {
stackmystack;
int PopIndex = 0;
for (int i=0; i<pushed.size(); i++){
mystack.push(pushed[i]);
while((!mystack.empty()) && (mystack.top() popped[PopIndex])){
mystack.pop();
PopIndex += 1;
}
}
return mystack.empty();
}
};

”’

0 赞同 0 条回复

Vow the vow。普通 2023年6月23日下午6:40

在每次入栈完，判断出栈数组是否为栈顶元素，是的话就模拟出栈操作。

public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for(int num : pushed){
            stack.push(num);
            // 相当于再此时调用出栈操作。模拟出栈。
            while(!stack.isEmpty() && stack.peek() == popped[i]){
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }

0 赞同 0 条回复

雨落圆荷普通 2023年6月23日下午4:52

class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
if(pushed null || pushed.length <= 0){
return true;
}
int k = 0;
Stack stack = new Stack();
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();
}
}
时间复杂度：O(n)
额外空间复杂度：O(n)

0 赞同 0 条回复

小吕普通 2023年6月23日下午4:45

c++实现
if(pushed.size()!=popped.size())return false;
stack st;
int len = pushed.size();
for(int i = 0,j=0;i<len;i++)
{
st.emplace(pushed[i]);
while(!st.empty()&&st.top()popped[j])
{
st.pop();
j++;
}
}
return st.empty();

0 赞同 0 条回复

Yodl. 普通 2023年6月23日下午3:05

简单模拟
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int>st;
        int cur=0;
        for(int i=0;i<pushed.size();++i)
        {
            st.push(pushed[i]);
            while(!st.empty()&&st.top()==popped[cur])
            { 
                st.pop();
                ++cur;
            }
        }
        return st.empty();
    }
};

0 赞同 0 条回复

jhfuture 普通 2023年6月23日下午3:00

 public boolean validateStackSequences(int[] pushed, int[] popped) {
        // 1.使用一个模拟栈实现
        //2.遍历 pushed依次进栈。同时判断加入的元素是否==popped的元素，如果等于则出栈，并且匹配下一个popped，不则继续进栈。
    Stack<Integer> stackA=new Stack();
    int k=0;
    for(int i=0;i<pushed.length;i++){
        stackA.push(pushed[i]);
        //这里判断不为空是因为如果 入栈是 1234，然后出栈可以是 21 34， 21 的时候栈就为空了，peek就直接为null
        while(!stackA.isEmpty()&&stackA.peek().intValue()==popped[k]){
                    stackA.pop();
                    k++;
        }
    }
    return stackA.isEmpty();

    }

多思考了一些点，为什么要为空。等
时间复杂度为n，空间复杂度为n.

0 赞同 0 条回复

　　　　　　　　普通 2023年6月23日下午2:04

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

【时间O(n),空间O(n)】
模拟栈操作
逐个压入元素
若当前元素与弹出元素相同，则循环弹出元素
判断栈空

0 赞同 0 条回复

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

共以下 49 个回答

复杂度

Code

# 回答此问题取消回复

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

共以下 49 个回答

复杂度

Code

# 回答此问题 取消回复

# 回答此问题取消回复