糖香香普通 2023年7月1日下午7:42

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

    }

0 赞同 0 条回复

宁永久会员 2023年3月16日下午4:54

模拟弹出过程

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed == null || pushed.length == 0) return true;
        //模仿栈的压入和弹出，如果最后不剩下元素就是弹出序列
        Stack<Integer> stack = new Stack<>();
        int popIndex = 0;
        for(int i = 0; i < pushed.length; i++){
            stack.push(pushed[i]);
            //Integer和int比较会进行自动拆箱，比较的是大小
            while(!stack.isEmpty() && stack.peek() == (popped[popIndex])){
                stack.pop();
                popIndex++;
            }
        }
        return stack.isEmpty();
    }
}

0 赞同 0 条回复

lucca 普通 2022年12月31日下午5:53

手动模拟

遍历push序列，依次加入栈中
如果栈顶和出栈序列匹配，就出栈
遍历结束后，栈应该为空，且入栈序列和出栈学列全部使用完毕

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int n = pushed.length;
        int[] s = new int[n];
        int top = -1;
        int idx = 0;
        for (int push : pushed) {
            s[++top] = push;
            while (top != -1 && s[top] == popped[idx]) {
                idx++;
                top--;
            }
        }
        return top == -1 && idx == n;
    }
}

0 赞同 0 条回复

hmmm 普通 2022年11月30日下午9:43

class Solution {
public:
stack<int> stack;
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        int j = 0; //记录popped数组的下标
        for(int i=0; i<pushed.size(); ++i)
        {
            stack.push(pushed[i]);
            while(!stack.empty() && stack.top() == popped[j]) //注意此处为while
            {
                stack.pop();
                ++j;
            }
        }
        if(stack.empty())
        return true;

        else 
        return false;
    }
};

时间复杂度和空间复杂度均为O(n)

0 赞同 0 条回复

努力刷题普通 2022年11月30日上午8:23

用一个辅助栈 与popped中的值比较
class Solution(object):
    def validateStackSequences(self, pushed, popped):
        """
        :type pushed: List[int]
        :type popped: List[int]
        :rtype: bool
        """
        stack = []
        i = 0
        for num in pushed:
            stack.append(num)
            while stack and stack[-1] == popped[i]:
                stack.pop(-1)
                i += 1
        return not stack

0 赞同 0 条回复

PatNick 普通 2022年11月20日下午4:30

def validateStackSequences(pushed: list[int], popped: list[int]) -> bool:
    '''
    使用一个辅助栈按照压栈顺序模拟，如果压入的值与出栈的值一样就模拟出栈，如果最终辅助栈中所有可以全部弹出，说明为true
    Args:
        pushed:
        popped:

    Returns:

    '''
    if not pushed:
        return True
    if len(pushed) == 1:
        return True
    help_list = []
    pop_index = 0
    for x in pushed:
        # 入栈
        help_list.append(x)
        # 如果出栈值与栈顶值一致就出栈（题中说入栈所有数字不相等）
        while (popped[pop_index] == help_list[-1]):
            help_list.pop()
            pop_index += 1
            # 这里防止辅助栈中为空而出界
            if not help_list:
                break


    if not help_list:
        return True
    else:
        return False

0 赞同 0 条回复

如梦似歌普通 2022年11月14日下午3:49

 // 时间复杂度: O(n) 其中n是数组pushed和popped的长度。需要遍历这两个数组各一次
 //空间复杂度: O(n) 空间复杂度主要取决于栈空间，栈内元素个数最多不超过n。
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque stack = new LinkedList();
        int j = 0;
        //遍历数组pushed，将pushed的每个元素依次入栈
        for (int i=0; i

0 赞同 0 条回复

🚲南下普通 2022年11月10日下午3:52

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

        if(pushed.size()==0){
            return true;
        }
        stack <int> stk; //辅助栈
        int size=pushed.size();
        int j = 0; //记录popped的栈顶元素
        for(int i = 0; i<size;i++){
            stk.push(pushed[i]);
            while(!stk.empty() && stk.top()==popped[j]){ 
                stk.pop();
                j++;
            }
        }
        return stk.empty();
    }
};

0 赞同 0 条回复

just 普通 2022年11月6日下午3:01

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

};

0 赞同 0 条回复

xye 普通 2022年11月3日下午7:39

时间复杂度O（n）空间复杂度O（n）

func validateStackSequences(pushed []int, popped []int) bool {
    st := []int{}
    j := 0
    for _, x := range pushed {
        st = append(st, x)
        for len(st) > 0 && st[len(st)-1] == popped[j] {
            st = st[:len(st)-1]
            j++
        }
    }
    return len(st) == 0
}

0 赞同 0 条回复

cute. 普通 2022年11月1日下午9:45

思路:
需要用到一个辅助栈进行，循环遍历pushed依次将其push到栈中，并循环判断是否与poped当前项一直，若一致则将将栈顶弹出pop，并递增i；若最后stack为空，则为true，不为空，则为false

/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
var validateStackSequences = function(pushed, popped) {
    let i = 0, stack = [];
    for(let val of pushed) {
        stack.push(val);
        /*判断 模拟栈的栈顶元素 是否跟 popped 数组此时要弹出的元素相等，相等的话模拟栈就弹出，
        popped 数组对应 i 指针向后移动一位
        */
        while(stack.length && stack[stack.length - 1] === popped[i]) {
            stack.pop();
            i += 1;
        }
    }
    // 如果在 pushed 数组全部元素都压入模拟栈后，模拟栈元素没随着 popped 清空，那么弹出序列对不上，返回 false
    return !stack.length;
};

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

0 赞同 0 条回复

一只骆驼普通 2022年11月1日下午8:50

循环判断与出栈,最后栈为空就证明成立

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

0 赞同 0 条回复

Asphyxia 普通 2022年11月1日下午5:32

栈模拟

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

0 赞同 0 条回复

Y7n05h 普通 2022年10月31日下午8:55

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        vector<int>stack;
        int seek=0;
        for(const auto i:pushed){
            stack.push_back(i);
            while(!stack.empty()&&stack.back()==popped[seek]){
                seek++;
                stack.pop_back();
            }
        }
        return stack.empty();
    }
};

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

0 赞同 0 条回复

王艺超普通 2022年10月31日下午8:12

依次每入栈一次序列就和出栈序列进行一次对比即可

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> st;

        for(int i = 0, j = 0; i < pushV.size();i++)
        {
            st.push(pushV[i]);
            while(!st.empty() && st.top() == popV[j])
            {
                st.pop();
                j++;
            }
        }
        if(st.empty()) return true;
        return false;
    }
};

0 赞同 0 条回复

cxxz 普通 2022年10月31日上午12:51

画了两遍图发现了规律，不断判断栈顶是否为 pop 序列的最头元素，来决定结下来是辅助栈是pop还是push。

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if (pushed.size() <= 0)
            return true;
        stack<int> sk;
        auto popit = popped.begin();

        for (auto x = pushed.begin(); x != pushed.end(); x++){
            sk.push(*x);
            while (!sk.empty() && sk.top() == *popit) {
                sk.pop();
                popit ++;
            }
        }
        return sk.empty();
    }
};

0 赞同 0 条回复

马啸天永久会员 2022年10月30日下午9:26

   public boolean validateStackSequences(int[] pushed , int[] popped) {
        //1.判断是否为null
        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 条回复

Ruby🗽 普通 2022年10月30日下午5:48

//辅助栈
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 条回复

symbol 普通 2022年10月30日下午3:39

func validateStackSequences(pushed []int, popped []int) bool {
    stack := []int{} //定义一个辅助栈
    k := 0
    for _, x := range pushed{
        //fmt.Println(x)
        stack = append(stack, x) //将pushed元素依次如栈
        //入栈之后判断栈顶元素和popped的第K个元素是否相等
        for len(stack) > 0 && popped[k] == stack[len(stack)-1]{
            //若相等则出栈
            stack = stack[:len(stack)-1]
            k++
        }
    }
    return len(stack) == 0
}

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

0 赞同 0 条回复

云雾里普通 2022年10月30日下午1:50

class Solution {
//辅助栈
    Stack<Integer> stack;
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        boolean result =  true;
        stack=new Stack<>();
        int index=0;
        int l2 = popped.length;
        for (int i = 0; i < pushed.length; i++) {
            if(index<l2 && !stack.isEmpty()&&stack.peek().equals(popped[index])){
                stack.pop();
                i--;
                index++;
                continue;
            }
            stack.push(pushed[i]);
        }
        while (!stack.isEmpty()&&index<l2){
            if(stack.pop().equals(popped[index])){
                index++;
            }else{
                result=false;
            }
        }
        return result;
    }
}

//辅助栈优化
public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int index=0;
        for (int x : pushed) {
            stack.push(x);
            while (!stack.isEmpty()&&stack.peek().equals(popped[index])){
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty();
    }

0 赞同 0 条回复

cxc 普通 2022年10月30日下午1:23

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<>();
        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 条回复

晨普通 2022年10月29日下午9:27

class Solution(object):
    def validateStackSequences(self, pushed, popped):
        """
        :type pushed: List[int]
        :type popped: List[int]
        :rtype: bool
        """
        # 判空
        if not pushed or not popped:
            return True

        stack = []
        k = 0
        for i in range(len(pushed)):
            stack.append(pushed[i])
            while len(stack) != 0 and stack[-1] == popped[k]:
                stack.pop()
                k += 1
        return len(stack) == 0

0 赞同 0 条回复

阿白普通 2022年10月29日下午3:03

1、通过临时栈来模拟入栈出栈顺序，如果最后栈空，则该顺序可行
2、时间O（n），空间O（n）

class Solution {
public:
    bool validateStackSequences(std::vector<int>& pushed, std::vector<int>& popped) {
        if ( pushed.size() <= 0)
            return true;
        std::stack<int> 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 条回复

潜行1 我是火车王！普通 2022年10月28日下午1:28

标准解法：借用辅助栈来模拟
时间：O(N)
空间：O(N)

func validateStackSequences(pushed []int, popped []int) bool {
    // use an assistant stack
    if pushed == nil || len(pushed) == 0 {
        return true
    }

    var stack []int
    var k int

    for i := 0; i < len(pushed); i++ {
        stack = append(stack, pushed[i])
        for len(stack) != 0 && stack[len(stack) - 1] == popped[k] {
            stack = stack[:len(stack)-1]
            k++
        }
    }

    if len(stack) == 0 {
        return true
    }
    return false
}

0 赞同 0 条回复

感到自己好渺小普通 2022年10月28日上午10:06

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        //思路：借用一个辅助栈来模拟压入和弹出的操作
        //入栈操作：按照压栈序列的顺序进行
        //出栈操作：每次入栈后，循环判断辅助栈中的栈顶元素 == 弹出序列中的当前元素是否相等，将符合弹出序列顺序的栈顶元素全部弹出
        //直到辅助栈中的元素全部弹出，说明弹出序列正确
                Stack<Integer> 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 条回复

派大星普通 2022年10月28日上午12:07

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

            }
            for(;j<popped.length&&popped[j]==stack.peek();j++){
                stack.pop();
            }
            return stack.isEmpty();

    }
}

0 赞同 0 条回复

酥合普通 2022年10月28日上午12:03

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

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

0 赞同 0 条回复

鸿渐普通 2022年10月27日下午10:50

时间： O(n)  空间 O(n)
  public static 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]);
            //开始判断，只要判断pop队列当中的头元素就行
            while(!stack.isEmpty() && stack.peek() == popped[k]){
                stack.pop();
                k++;
            }
        }
        return stack.isEmpty();
    }

0 赞同 0 条回复

单个酒窝儿普通 2022年10月27日下午9:50

1、先判断特殊情况，如果数组为空或者数组内元素个数为0是，直接返回true
2、利用一个for循环将元素压入栈中，每个元素压入栈中的过程中，判断栈顶元素是否与出栈顺序的元素相等，如果相等则栈中元素出栈
时间复杂度O(n) 空间复杂度O(n)

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if(pushed.empty() || pushed.size() <= 0) return true;

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

0 赞同 0 条回复

狗蛋儿普通 2022年10月27日下午9:29

开了一个新栈o(n),时间复杂度也是o(n)

class Solution {
public:
    //题目的核心思想就是按照出栈的顺序去模拟一个入栈的顺序
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        //首先求出来要压入栈的数据大小
        int n = pushV.size();
        stack<int> moni;
        //j是看是否全部的数据已经压入
        int j = 0;
        //遍历的对象是弹出顺序
        for(int i = 0; i<popV.size();i++){
            //这里比较麻烦的就是while里面的多条件判断
            //首先应该想明白整个流程，然后再补判断条件
            while(j<n && (moni.empty() || moni.top() != popV[i])){
                moni.push(pushV[j]);
                j++;
            }
            if(moni.top() == popV[i]) moni.pop();
            else return false;
        }
        return true;
    }
};

0 赞同 0 条回复

优秀市民普通 2022年10月27日下午9:25

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

时间复杂度o(n)空间复杂度o(n)
用一个辅助栈，先按顺序将pushed中的元素入栈，入栈后判断入栈的元素是否与poped的第一个元素相同，若相同则出栈，poped后移一位，知道pushed的元素全部入栈

0 赞同 0 条回复

lobort 普通 2022年10月27日下午8:12

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
//直接利用栈的特性来解题
        Stack<Integer> stack = new Stack<>();
        // 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();
    }
}

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

0 赞同 0 条回复

@ 普通 2022年10月27日下午8:08

思路：
借用一个辅助栈 stack ，模拟压入 / 弹出操作的排列。根据是否模拟成功，即可得到结果。
入栈操作：按照压栈序列的顺序执行。
出栈操作：每次入栈后，循环判断 “栈顶元素弹出序列的当前元素” 是否成立，将符合弹出序列顺序的栈顶元素全部弹出。
判断：最后根据该栈是否为空来判断是否是正确的压入/弹出操，为空，说明栈的出栈顺序是正确的，否则为错误的。
时间复杂的：O(n) 空间复杂的：O(n)

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque stack = new ArrayDeque<>();

        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 条回复

追普通 2022年10月27日下午6:55

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

注意：不是等所有元素全部入栈之后再出栈，可以在入栈的某一时刻之后出栈，只要能按照出栈顺序即可

0 赞同 0 条回复

星河普通 2022年10月27日下午6:35

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for(int num : pushed) {
            stack.push(num); // num 入栈
            while(!stack.isEmpty() && stack.peek() == popped[i]) { // 循环判断与出栈
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}
时间O(N)空间O(N)

0 赞同 0 条回复

庄重普通 2022年10月27日下午6:05

// 思路：
//     栈的pushed和poped只有唯一解，只要模拟出如何poped的顺序出栈
//     判断栈是否为空,空的时候即为正常出栈，遵循唯一解
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if (pushed.empty() || pushed.size() < 0) return true;

        stack<int> staTmp;
        int j = 0;
        for (int i = 0; i < pushed.size(); ++i) {
            staTmp.push(pushed[i]);
            for(; !staTmp.empty() && staTmp.top() == popped[j]; ++j) {
                //for中的两个条件不能改变顺序
                //栈为空的时候，就不存在栈顶元素，链接时会报错
                staTmp.pop();
            }
        }
        return staTmp.empty();

    }
};
//时间复杂度O(n)
//空间复杂度O(n) 辅助栈的空间

0 赞同 0 条回复

Tolkien 永久会员 2022年10月27日下午4:45

模拟栈
1. 时间复杂度：O(n)
2. 空间复杂度：O(n)
3. 代码

/**
     * 给定第一个序列为栈的压入顺序，若第二个序列是弹出顺序，
     * 则要满足 该栈完成以上所有压入和弹出操作后，栈为空。
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();

        // 遍历入栈数组和出栈数组，以模拟栈完成所有的入栈和出栈操作
        for (int i = 0, j = 0; i < pushed.length; i++) {
            // 1. 将压栈元素入栈
            stack.push(pushed[i]);

            // 2. 若出栈元素与当前栈顶元素相同，则出栈
            while (!stack.isEmpty() && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }

        // 3. 栈为空，则说明该栈能够完成以上所有压入和弹出操作
        return stack.isEmpty();
    }

0 赞同 0 条回复

mpweixin用户永久会员 2022年10月27日下午4:43

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<Integer>();
        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();
    }
}

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

0 赞同 0 条回复

小肸永久会员 2022年10月27日下午4:36

思路一：栈模拟。时间复杂度和空间复杂度都为O(N)。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed.length != popped.length) {
            return false;
        }
        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();
    }
}

思路二:leetcode看到的，一组合法的入栈、出栈顺序对应二叉树的前序、中序遍历。所以直接根据pushed和poped两个数组判断能否构成一颗二叉树来判断结果就行。时间复杂度的话，递归调用次数n次，每一次递归的时间复杂度O(N)，所以总的时间复杂度为O(N^2)，空间复杂度的话，O(N)吧。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        return validateCore(pushed, 0, pushed.length - 1, popped, 0, popped.length - 1);
    }
    private boolean validateCore(int[] pre, int leftPre, int rightPre, int[] in, int leftIn, int rightIn) {
        if (leftPre > rightPre || leftIn > rightIn) {
            return true;
        }
        Set<Integer> set = new HashSet<>();
        for (int i = leftPre; i <= rightPre; i ++) {
            set.add(pre[i]);
        }
        for (int i = leftIn; i <= rightIn; i ++) {
            if (!set.contains(in[i])) {
                return false;
            }
        }
        int root = pre[leftPre];
        int rootInIndex = leftIn;
        while (in[rootInIndex] != root) {
            if (rootInIndex > rightIn) {
                return false;
            }
            rootInIndex ++;
        }
        return validateCore(pre, leftPre + 1, leftPre + (rootInIndex - leftIn), in, leftIn, rootInIndex - 1) && validateCore(pre, leftPre + (rootInIndex - leftIn) + 1, rightPre, in, rootInIndex+1,rightIn); 
    }
}

思路三：牛客网看到的一种，因为数组类似与栈，直接用数组的下标作为栈顶的定位符，在pushed数组上修改。时间复杂度O(n)，空间复杂度O(1)。

0 赞同 0 条回复

Chin 普通 2022年10月27日下午4:36

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

时空复杂度On

0 赞同 0 条回复

Haoyun 普通 2022年10月27日下午3:16

var validateStackSequences = function(pushed, popped) {
   let stack = [];
   for(let i = 0, j = 0; i < pushed.length; i++) {
//将pushed每个元素依次入栈
       stack.push(pushed[i]);
//当栈不为空，比较栈顶和popped数组里的元素，直到栈为空或者两者不同
       while(stack.length && stack[stack.length - 1] === popped[j]) {
           stack.pop();
           j++;
       }
   }
   return !stack.length;
};

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

0 赞同 0 条回复

虾仁猪心普通 2022年10月27日下午2:17

1.题目解读

由题目可知入栈的所有数字均不相等，因此在循环入栈中，每个元素出栈的位置的可能性是唯一的（若有重复数字，则具有多个可出栈的位置）。因而，在遇到栈顶元素与弹出序列的当前元素的值相同时就应立即执行出栈。
参考作者：jyd

思路：

初始化一个辅助栈，出栈索引 i
2.循环参数列表入栈的数组进行循环入栈
3.循环入栈的操作中按照出栈的数组元素，判断是否与栈顶元素相同，若相同则执行出栈操作，并且i++.
返回辅助栈.isEmpty()；true则表示可以按照参数中的出栈顺序出栈，false就是不可以。

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

0 赞同 0 条回复

刺猬普通 2022年10月27日上午11:39

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

模拟栈的进出，最后判断栈是否为空
时间复杂度O(N)
空间复杂度O(N)

0 赞同 0 条回复

天然普通 2022年10月27日上午11:34

用一个lst来接收栈底元素，lst判断是否和出栈元素相同，相同lst.pop(),否则继续循环，直到栈空 return not lst
时间复杂度O(n)
空间复杂度O(n)

class Solution(object):
    def validateStackSequences(self, pushed, popped):
        """
        :type pushed: List[int]
        :type popped: List[int]
        :rtype: bool
        """
        lst1,i= [],0
        for num in pushed:
            lst1.append(num)
            while lst1 and lst1[-1]==popped[i]:
                lst1.pop()
                i+=1

        return not lst1

0 赞同 0 条回复

黎昕普通 2022年10月27日上午11:07

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

解法思路

使用一个足够的数组模拟栈，初始化front=rear=0，pushindex=popindex=0，pushindex用于遍历pushed序列，popindex用于遍历popped序列。

栈空时，按照pushed序列入栈；非空时，判断当前栈顶元素与当前需要出栈的元素（即popped序列中popindex指向元素）是否相同，相同则出栈并将popindex后移；不同则继续压栈。直到压栈完毕（pushed序列遍历完）。

由于pushed序列一定先于或者同时于popped序列遍历完，所以需要继续遍历popped序列，如果当前栈顶元素与popped序列中即将出栈元素不同，返回false，否则出栈直到popped序列结束。

上述过程中都没有返回false，证明正确，返回true。

时间复杂度 O(n)

相当于遍历一遍pushed序列与popped序列，所以为O(n)。

空间复杂度 O(n)

虽然这里直接定义了1001大小的数组，但是实际上与序列长度正相关，定义1001是为了解题方便。

leetcode beats

时间：100%
空间：91.21%

代码

代码实现

#define MAX_LENGTH 1001
bool validateStackSequences(int* pushed, int pushedSize, int* popped, int poppedSize){
    //模拟解法
    //思路：定义一个stackarr用于模拟栈，front指向栈底（本题中可直接为0），rear指向栈顶即将压入的位置，当rear==front时，栈空
    int stackarr[MAX_LENGTH];
    int front=0;
    int rear=0;
    int pushindex=0;//用于遍历pushed序列
    int popindex=0;//用于遍历poped序列
    //模拟
    for(int pushinedx=0;pushindex < pushedSize;){
        if(rear==front){//栈空
            stackarr[rear++]=pushed[pushindex++];
        }else if(popped[popindex]!=stackarr[rear-1]){//按照pop序列 当前要出栈的元素并不在栈顶，继续压栈
            stackarr[rear++]=pushed[pushindex++];
        }else{//相等时 出栈
            rear--;//出栈
            popindex++;//出栈序列向后遍历
        }
    }
    //一定是压栈序列先遍历完，或者压栈与出栈同时遍历完
    while(rear!=front){
        if(stackarr[rear-1]!=popped[popindex]){//出栈序列不可能达到
            return false;
        }else{//继续出栈
            rear--;
            popindex++;
        }
    }
    return true;
}

0 赞同 0 条回复

是梦终空永久会员 2022年10月27日上午10:52

循环遍历并且入栈，然后判断是否和第二个数组的j位置的值相等，相等就出栈，不相等就再遍历入栈
时间O(n)
空间O(n)

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

0 赞同 0 条回复

绍熙普通 2022年10月27日上午10:41

算法流程：
初始化：辅助栈 stackstack ，弹出序列的索引 ii ；
遍历压栈序列：各元素记为 numnum ；
元素 numnum 入栈；
循环出栈：若 stackstack 的栈顶元素弹出序列元素 popped[i]popped[i] ，则执行出栈与 i++i++ ；
返回值：若 stackstack 为空，则此弹出序列合法。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for(int num : pushed) {
            stack.push(num); // num 入栈
            while(!stack.isEmpty() && stack.peek() == popped[i]) { // 循环判断与出栈
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}

0 赞同 0 条回复

你有点可爱喔普通 2022年10月27日上午10:37

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

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

    }
}

0 赞同 0 条回复

wxc 普通 2022年10月27日上午10:04

额

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        if(len(pushed) == 0):
            return True
        s = []
        i = 0
        for x in pushed:
            s.append(x)
            while s and s[-1] == popped[i]:
                s.pop()
                i += 1
        return len(s) == 0

0 赞同 0 条回复

浅夏的无奈普通 2022年10月27日上午12:10

用一个辅助栈，把pushed中的元素，push到辅助栈中，判断辅助栈顶元素是否与当前poped[j]相等，如果相等就进行pop操作，然后把j+1，运行完后，判断栈是否为空。
时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
         Deque<Integer> stack = new ArrayDeque<Integer>();
        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 条回复

Error 普通 2022年10月27日上午12:07

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        # 辅助栈 模拟入栈操作
        stack = []
        # popped栈的指针
        i = 0
        for n in pushed:
            stack.append(n)
            while stack and stack[-1] == popped[i]:
                stack.pop()
                i += 1
        return not stack

时间复杂度 O(nlogn)

0 赞同 0 条回复

Gg 普通 2022年10月26日下午11:53

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        // 借助辅助栈进行模拟。遍历pushed进行压入，当压入的元素等于popped上的元素，从栈上弹出
        Stack<Integer> stk = new Stack<>();
        int poppedIndex = 0;
        for(int p : pushed){
            stk.push(p);
            while(!stk.isEmpty() && stk.peek() == popped[poppedIndex]){
                stk.pop();
                poppedIndex++;
            }
        }
        return stk.isEmpty();
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月26日下午11:44

/*
时间复杂度O(n)
空间复杂度O(n)辅助栈
*/

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed == null || pushed.length < 0) return false;
        if(pushed.length != popped.length) return false;
        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+1 stack弹出
                k++;
            }
        }
        return stack.isEmpty();
    }
}

0 赞同 0 条回复

yanshuojune 普通 2022年10月26日下午11:14

解题思路：构建辅助栈，遍历pushed中的元素，并push到辅助栈中，当辅助栈栈顶元素和当前poped[j]相等时，就对辅助栈执行pop操作，并将j+1，执行完操作查看辅助栈是否为空，判断poped是否未pushed的弹出序列。
时间复杂度：O(n)
空间复杂度：O(n)

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

0 赞同 0 条回复

猫猫真可爱普通 2022年10月26日下午11:04

用一个栈来实现，定义一个j来定位popped【】里面的数据，即（出栈的数据）。stack为空就进行入栈操作，然后判断栈顶元素与popped【j】是否相等，相等stack出栈并且j加一（popped序列往后走），不相等就继续进行入栈操作。每次入栈操作后重复上一步。直到pushed【】遍历完。如果popped序列正确，stack就是空的，所以直接返回stack的判空方法。

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

0 赞同 0 条回复

青木普通 2022年10月26日下午10:56

// 看了官解感觉自己写的是个...
// 比较丑陋，思路是用一个栈进行模拟
// 时间复杂度O(n)
// 空间复杂度O(n)

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> s = new ArrayDeque<>();
        int i=0, j=0, n=pushed.length; // i记录pushed下标， j记录popped下标
        while(j<n){
            // 当栈空，或栈顶元素和pop数组遍历值不同，从i开始将push数组的值压进s
            if(s.isEmpty() || s.peek()!=popped[j]){
                while(i<n && pushed[i]!=popped[j]){
                    s.push(pushed[i]);
                    i+=1;
                }
                i+=1;
                j+=1;
                //如果i超过终点了j还没有，说明错误
                if(i>n && j<n) return false;
            }
            // 反之弹栈
            else if(popped[j] == s.peek()){
                s.pop();
                j+=1;
            }
        }
        return true;
    }
}

//官解，代码太简洁了
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> s = new ArrayDeque<>();
        int n = pushed.length;
        for(int i=0, j=0; i<n; i++){
            s.push(pushed[i]);
            while(!s.isEmpty() && s.peek() == popped[j]){
                j++;
                s.pop();
            }
        }
        return s.isEmpty();
    }
}

0 赞同 0 条回复

So 普通 2022年10月26日下午9:42

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed == null) {
            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();
    }
}

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

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年10月26日下午9:35

利用规则一个元素入栈，他之前入栈的元素的顺序的逆序的相对顺序不变，创建一个栈模拟操作，具体详细见代码，时间空间复杂度都为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().intValue()==popped[k]){
                stack.pop();
                k++;
            }

        }
        return stack.isEmpty();
    }
}

0 赞同 0 条回复

Whatever 永久会员 2022年10月26日下午8:25

先按序入栈，并判断是否有元素符合出栈序列，如果循环结束栈为空，代表出入栈序列相符合。时间O(n)，空间O(n)

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

0 赞同 0 条回复

T 普通 2022年10月26日下午5:54

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        // 创建stack模拟入栈出栈效果
        LinkedList<Integer> stack = new LinkedList<>();
        int flag = 0;
        for(int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            // 如果栈不为空且栈顶元素和pop数组当前位置元素相同就弹出，flag增加。
            while(!stack.isEmpty() && stack.peek().equals(popped[flag])) {
                stack.pop();
                flag++;
            }
        }
        //如果为空则成功
        return stack.isEmpty();
    }
}

0 赞同 0 条回复

波波_1936 普通 2022年10月26日下午4:42

 public boolean validateStackSequences(int[] pushed, int[] popped) {
//        时间复杂度 O(n)
//        空间复杂度O(n)
//        执行用时：3 ms, 在所有 Java 提交中击败了 61.61% 的用户
//        内存消耗：41.4 MB, 在所有 Java 提交中击败了 24.45% 的用户
        if (pushed != null && popped == null) return false;
        if (pushed == null && popped != null) return false;
        if (pushed.length != popped.length) return false;

        //使用模拟法
        //如果当前push的值和当前pop出的值不一致则继续push 一致则pop同时popped 的index移动
        int popIndex = 0;
        int pushIndex = 0;

        Stack<Integer> stack = new Stack<>();
        while (pushIndex < pushed.length) {
            int pV = pushed[pushIndex];
//            if (stack.isEmpty()) {
            stack.push(pV);
            pushIndex++;
//            }
            while (!stack.isEmpty() && popIndex < popped.length && popped[popIndex] == stack.peek()) {
                stack.pop();
                popIndex++;
            }

        }
        return stack.isEmpty() && pushIndex == pushed.length && popIndex == popped.length;
    }

0 赞同 0 条回复

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

共以下 61 个回答

手动模拟

1.题目解读

思路：

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

解法思路

时间复杂度 O(n)

空间复杂度 O(n)

leetcode beats

代码

# 回答此问题取消回复

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

共以下 61 个回答

手动模拟

1.题目解读

思路：

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

解法思路

时间复杂度 O(n)

空间复杂度 O(n)

leetcode beats

代码

# 回答此问题 取消回复

# 回答此问题取消回复