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

Laboratory 普通 2024年4月15日下午11:29

class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        if(putIn.length == 0) {
            return true;
        }
        Deque<Integer> stack = new LinkedList<>();
        int i=0;
        for(int num : putIn) {
            stack.offerLast(num);
            while(!stack.isEmpty() && stack.peekLast() == takeOut[i]) {
                stack.pollLast();
                i++;
            }
        }
        return stack.isEmpty();
    }
}

时间复杂度O（n）,空间复杂度O(n)

0 赞同 0 条回复

山月普通 2024年3月16日下午4:22

//栈的压入和弹出
//看到之后都读不太懂题目，还是练习的太少了
//还是借用了辅助栈，入栈每一个元素的同时循环判断取出序列组是否有相同的元素
class Solution {
public:
bool validateBookSequences(vector& putIn, vector& takeOut) {
stack stk;
int i = 0;
for(int num:putIn)
{
stk.push(num);
while(!stk.empty() && stk.top() takeOut[i])
{//循环判断出栈
stk.pop();
i++;

        }
    }
    return stk.empty();
}

};

0 赞同 0 条回复

YOLO 普通 2024年3月14日上午10:54

//输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        if(putIn == null || putIn.length <= 0){
            return true;
        }
        int k = 0;
        Stack<Integer> stack = new Stack();
        for(int i = 0 ;i < putIn.length;i++){
            stack.push(putIn[i]);
            while(!stack.isEmpty() && stack.peek() == takeOut[k]){
                stack.pop();
                k++;
            }
        }
        return stack.isEmpty();
    }
}

0 赞同 0 条回复

！。！普通 2024年3月13日上午10:44

”’java
class Solution {
public:
bool validateBookSequences(vector& putIn, vector& takeOut) {
stack stk;
int i = 0;
for(int num : putIn){
stk.push(num);
while(!stk.empty() && stk.top()takeOut[i]){
stk.pop();
i++;
}
}
return stk.empty();
}
};
”’
时间复杂度：o(n)
空间复杂度：o(n)

0 赞同 0 条回复

晚风、普通 2024年3月13日上午12:30

def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:
stack,i = [],0
for num in putIn:
stack.append(num)
while stack and stack[-1] takeOut[i]:
stack.pop()
i = i+1

    return not stack

解题思路：
使用辅助栈依次压入要Putin的数据
然后确认辅助栈不为空且每次都检查一下是否跟takeout[i]相同，如果相同则将辅助栈顶元素pop出去,且i=i+1
时间复杂度：o(n)
空间复杂度：o(n)

0 赞同 0 条回复

一颗红豆普通 2024年3月11日上午11:18

建立一个辅助栈，以元素出现顺序出栈，看最终的栈空间是否为空
时间复杂度o（n）空间复杂度o（n）
class Solution {
public:
bool validateBookSequences(vector& putIn, vector& takeOut) {
std::stack s1;
int k = 0;
for(int a=0;a<putIn.size();a++)
{
s1.push(putIn[a]);
while(!s1.empty()&&takeOut[k]s1.top())
{
s1.pop();
k++;
}
}
if(s1.empty())
{
return true;
}
else
{
return false;
}
}
};

0 赞同 0 条回复

MARS 普通 2024年3月10日下午11:08

day5第二题

function validateBookSequences(putIn: number[], takeOut: number[]): boolean {
    let stack=[]
    let i=0

    for(let num of putIn){
        stack.push(num)
        while( stack.length>0 && stack[stack.length-1] == takeOut[i] ){
            stack.pop()
            i++
        }
    }
    return i ==takeOut.length
};

0 赞同 0 条回复

e=mc² 普通 2024年3月9日下午10:00

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

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

0 赞同 0 条回复

helloMoon 普通 2024年3月9日下午8:45

栈的压入、弹出序列java

class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        if(putIn == null || putIn.length <= 0){
            return true;
        }

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

0 赞同 0 条回复

零普通 2024年3月9日下午8:41

思路：利用栈的先入后出特性，每次将存书序列入栈，同时去判断当前的栈顶是否和当前要取出的书是否相同，相同就取出，即出栈，同时取书序列向后一位，如果最终栈为空，则取书序列是合法的
代码：


    public boolean validateBookSequences(int[] putIn,int[] takeOut) {
        Stack stack = new Stack<>();
        int index = 0;
        for (int val1 : putIn) {
            stack.push(val1);
            while(!stack.empty() && stack.peek() == takeOut[index]) {
                stack.pop();
                ++index;
            }
        }
        return stack.empty();
    }

0 赞同 0 条回复

普通 2024年3月9日下午8:13

class Solution {
public:
bool validateBookSequences(vector& putIn, vector& takeOut) {
stack stk;
if(putIn.size()0) return true;

    int k=0;
    for(int ii=0;ii<putIn.size();ii++)
    {
        stk.push(putIn[ii]);
        while(!stk.empty()&&stk.top()==takeOut[k])
        {
            stk.pop();
            k++;
        }
    }
    return stk.empty();
}

};
打卡

0 赞同 0 条回复

莫～慢～待普通 2024年3月9日下午5:48

class Solution {
public boolean validateBookSequences(int[] putIn, int[] takeOut) {
Stack zhan=new Stack<>();
int k=0;
for(int i=0;i<putIn.length;i++)
{
zhan.push(putIn[i]);
while(!zhan.isEmpty()&&zhan.peek().intValue()takeOut[k])
{
zhan.pop();
k++;
}
}
return zhan.isEmpty();
}
}
模拟

0 赞同 0 条回复

东普通 2024年3月8日下午4:43

//使用一个栈来处理 pushed 数组，每次将 pushed[i]pushed[i]pushed[i] 放入栈中，然后比较当前栈顶元素是否与待弹出元素相同（使用变量 j 来代指当前待弹出元素下标），若相等则弹栈并进行 j 自增，当所有的元素处理完后，栈为空说明栈序列合法。


class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> d = new ArrayDeque<>();
        for(int i = 0,j = 0;i < pushed.length; i++){
            d.addLast(pushed[i]);
            while(!d.isEmpty() && d.peekLast() == popped[j]){
                d.pollLast();
                j++;
            }
        }
        return d.isEmpty();
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年3月7日下午9:56

java
class Solution {
public boolean validateBookSequences(int[] putIn, int[] takeOut) {
Stack 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 条回复

　南木普通 2024年3月7日下午5:46

就是栈，判断最后是否栈空，时间复杂度O（n），空间复杂度O(n)

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

0 赞同 0 条回复

墨丘俐普通 2024年3月7日下午5:33

class Solution {
public boolean validateBookSequences(int[] putIn, int[] takeOut) {
Stack stack = new Stack();
int index = 0;
for(int i = 0;i<putIn.length;i++){

        stack.push(putIn[i]);
        while(!stack.isEmpty()&&stack.peek() == takeOut[index]){
            stack.pop();
            index++;

        }



    }
    if(!stack.isEmpty()){
        return false;

    }
    return true;

}

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

0 赞同 0 条回复

Let it be 永久会员 2024年3月7日下午4:39

class Solution {
public boolean validateBookSequences(int[] putIn, int[] takeOut) {
Stack A = new Stack();
int i = 0;
for(int num:putIn){
A.push(num);
while(!A.isEmpty() && A.peek() takeOut[i]){
A.pop();
i++;
}
}
return A.isEmpty();
}
}时间复杂度O（n），空间复杂度O（n）

0 赞同 0 条回复

kfaebot 普通 2024年3月7日上午11:17

class Solution {
public:
    bool validateBookSequences(vector<int>& putIn, vector<int>& takeOut) {
        stack<int>books;

        int pt=0;
        for(int i=0;i<putIn.size();i++){
            //先将元素入栈
            books.push(putIn[i]);
            //循环判断拿取顺序是否一致
            while(!books.empty()&&books.top()==takeOut[pt]){
                books.pop();
                pt++;
            }
        }
        return books.empty();
    }
};
//时间复杂度O(N)
//空间复杂度O(N)

0 赞同 0 条回复

紫芝普通 2024年3月7日上午8:17

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

func validateBookSequences(putIn []int, takeOut []int) bool {
    var tmpstack []int
    Oidx := 0
    for _, val := range putIn {
        if val == takeOut[Oidx] {
            Oidx++
            for len(tmpstack) > 0 && Oidx < len(takeOut) && tmpstack[len(tmpstack)-1] == takeOut[Oidx] {
                tmpstack = tmpstack[:len(tmpstack)-1]
                Oidx++
            }
            continue
        }
        tmpstack = append(tmpstack, val)

    }
    return len(tmpstack) == 0
}

0 赞同 0 条回复

HU 普通 2024年3月7日上午6:43

/**
 * @param {number[]} putIn
 * @param {number[]} takeOut
 * @return {boolean}
 */
var validateBookSequences = function(putIn, takeOut) {
    let stack = [];
    let k = 0;

    for(let i = 0; i < putIn.length; i++) {
        // 首先执行压栈
        stack.push(putIn[i]);
        while(stack.length > 0 && stack.slice(-1)[0] == takeOut[k]) {
            // stack有元素，并且stack的栈顶元素等于takeOut当前指向的元素的值
            stack.pop();
            k++;
        }
    }

    return stack.length == 0;
};

0 赞同 0 条回复

南梁陈庆之普通 2024年3月7日上午12:13

栈结构，先后后出

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

        }
        if (i != j) {
            return false;
        } else {
            return true;
        }
    }
}

0 赞同 0 条回复

神经蛙普通 2024年3月7日上午12:04

class Solution {
public:
bool validateBookSequences(vector& putIn, vector& takeOut) {
stackstk;
int i = 0;
for(int num : putIn)
{
stk.push(num);
while(!stk.empty() && stk.top() takeOut[i])
{
stk.pop();
i++;
}
}
return stk.empty();
}
};
打卡

0 赞同 0 条回复

叫不醒装睡的人普通 2024年3月6日下午10:24

class Solution {
    // 按照顺序进行入栈操作
    // 每个元素入栈时，判断栈顶元素与出栈顺序下元素是否相同
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        if (putIn == null || takeOut == null) {
            return true;
        }
        int idx = 0;
        Stack<Integer> stack = new Stack<>();
        for (int element : putIn) {
            stack.push(element);
            while (!stack.isEmpty() && stack.peek() == takeOut[idx]) {
                idx++;
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
    // 时间复杂度为 O(n)
    // 空间复杂度为 O(n)
}

0 赞同 0 条回复

NULL 普通 2024年3月6日下午9:25

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

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

0 赞同 0 条回复

Free 普通 2024年3月6日下午8:53

class Solution 
{
public:
    bool validateBookSequences(vector<int>& putIn, vector<int>& takeOut) 
    {
        stack<int> sk;
        int i = 0;
        for(auto e : putIn)
        {
            sk.push(e);
            while(!sk.empty() && sk.top() == takeOut[i])
            {
                sk.pop();
                i++;
            }
        }a
        return sk.empty();
    }
};

时空复杂度O(N)

0 赞同 0 条回复

云无深雁影普通 2024年3月6日下午6:54

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

    return s.empty();

}

}
//时间复杂度On
//空间复杂度On

0 赞同 0 条回复

Jimmy 普通 2024年3月6日下午5:53

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

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

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

0 赞同 0 条回复

Jankin 普通 2024年3月6日下午5:45

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

    }
}

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

0 赞同 0 条回复

Yuki 永久会员 2024年3月6日下午1:52

打卡
https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/solutions/2670683/yan-zheng-tu-shu-qu-chu-shun-xu-by-yukis-vhzv

0 赞同 0 条回复

mpweixin用户普通 2024年3月6日下午1:31

public boolean validateBookSequences(int[] putIn, int[] takeOut) {
Stack A= new Stack<>();
int j=0;
if(putIn.length0||putIn.length1) return true;
for(int num:putIn){
A.push(num);
while(!A.isEmpty() && A.peek()takeOut[j]){
A.pop();
j++;
}
}
return A.isEmpty();

思路：每个字符都压栈，遇到和输出字符一样的再重复出栈，最后看栈是否为空

0 赞同 0 条回复

ChenZhangHangTime 永久会员 2024年3月6日上午10:25

核心点在于理解压入弹出序列的知识（我之前学过关于这个知识点，所以理解起来不难），还有要创建一个辅助栈
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();
}

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月6日上午10:23

class Solution {
public:
    // 使用一个辅助栈，然后把putIn数组入栈，每入一个数字，就循环比较栈顶和takeOut数组头部是否相等
    // 若相等，则说明该数字可以在此时出栈
    // 若遍历完putIn数组之后，辅助栈中仍有元素，说明takeOut数组中某些数字的出栈顺序不可以
    bool validateBookSequences(vector<int>& putIn, vector<int>& takeOut) {
        stack<int> stk;
        int i = 0;
        for(int num : putIn) {
            stk.push(num);
            while(!stk.empty() && stk.top() == takeOut[i]) {
                stk.pop();
                ++i;
            }
        }
        return stk.empty();
    }
};

0 赞同 0 条回复

进取普通 2024年3月6日上午9:42

class Solution {
public:
bool validateBookSequences(vector& putIn, vector& takeOut) {
stack st;
int i = 0;
for (auto num : putIn){
st.push(num);
while (!st.empty() && st.top() takeOut[i]){
st.pop();
++i;
}
}
return st.empty();
}
};输入和输出用栈来维护，时空复杂度都是O(N)

0 赞同 0 条回复

Yox 普通 2024年3月6日上午3:00

class Solution:
def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:
stack, i = [],0
for num in putIn:
stack.append(num)
while stack and takeOut[i] stack[-1]:
stack.pop()
i += 1
return not stack
时间 o（N）空间O（N）

0 赞同 0 条回复

Raphtalia. 普通 2024年3月6日上午1:20

class Solution {
public:
bool validateBookSequences(vector& putIn, vector& takeOut) {
stack s1;
int j = 0;
for(int i = 0; i < putIn.size(); i ++){
s1.push(putIn[i]);
while(!s1.empty() && s1.top() takeOut[j]){
s1.pop();
j ++;
}
}
return s1.empty();
}
};
时间复杂度空间复杂度均为O（n）

0 赞同 0 条回复

机电皮怪永久会员 2024年3月5日下午11:48

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

“`C++
class Solution {
public:
bool validateBookSequences(vector& putIn, vector& takeOut) {
if(putIn.empty() == true)
{
return true;
}

    stack<int> sta;
    for(int i = 0, k = 0; i < putIn.size(); i++)
    {
        sta.push(putIn[i]);
        while(sta.empty() == false && sta.top() == takeOut[k])
        {
            sta.pop();
            k++;
        }
    }
    return sta.empty();
}

};

“`

0 赞同 0 条回复

=.= 普通 2024年3月5日下午11:08

class Solution {
public boolean validateBookSequences(int[] putIn, int[] takeOut) {
int index1 = 0;
int index2 = 0;
int m = putIn.length;
int n = takeOut.length;
Deque stack = new ArrayDeque<>();

    while(index1 < m){
        stack.addLast(putIn[index1]);
        while(!stack.isEmpty() && stack.getLast() == takeOut[index2]){
            stack.removeLast();
            index2++;
        }
        index1++;
    }

    return stack.isEmpty();
}

}

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

0 赞同 0 条回复

方铎码农普通 2024年3月5日下午10:00

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

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

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月5日下午9:59

class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        if(putIn==null || putIn.length <=0) return true;

        Stack<Integer> stack;
        stack = new Stack();
        int in=0;
        int out=0;
// 时间复杂度：O(n)
// 额外空间复杂度：O(n)
        for(int i=0;i<putIn.length;i++){
            stack.push(putIn[i]);
            while(!stack.isEmpty() && stack.peek()==takeOut[out]){
                stack.pop();
                out++;
            }
        }
// 超出内存限制
        // while(in<putIn.length || out < takeOut.length){
        //     if(stack.isEmpty()) {
        //         stack.push(putIn[in]);
        //         if(in<putIn.length-1) in++;
        //     }
        //     while(stack.peek()!=takeOut[out]){
        //         stack.push(putIn[in]);
        //         if(in<putIn.length-1) in++;
        //     }
        //     if(!stack.isEmpty() && stack.peek()==takeOut[out]){
        //         stack.pop();
        //         if(out <takeOut.length-1) out++;
        //     }
        // }

        return stack.isEmpty();


    }
}

0 赞同 0 条回复

王位詮釋普通 2024年3月5日下午9:02

class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        Deque<Integer> deque = new LinkedList<>();
        int length = putIn.length;
        int j = 0;
        for(int i=0;i<putIn.length;i++){
            deque.push(putIn[i]);
            while(j<length&&deque.peek().equals(takeOut[j])){
                deque.pop();
                j++;
                if(deque.isEmpty()){
                    break;
                }
            }
        }
        return deque.isEmpty();
    }
}

按照顺序进栈，然后比较出的顺序，如果出的值与栈顶元素相等就出栈，时间复杂度：O(n)，空间复杂度：O(n)

0 赞同 0 条回复

言之命至普通 2024年3月5日下午8:56

我们按照顺序入栈和出栈，如果最后栈空，则返回true；否则反馈false;

class Solution {

    public boolean validateBookSequences (int[] pushed, int[] popped) {
   if(pushed == null || pushed.length <= 0){
            return true;
        }//因为 pushed.length == popped.length ，所以只判断一个就够了
        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 条回复

heathhou 普通 2024年3月5日下午8:41

class Solution {
public:
    bool validateBookSequences(vector& putIn, vector& takeOut) {
        if(putIn.empty()){
            return true;
        }

        stack s;
        int k = 0;
        for(int i = 0; i < putIn.size(); ++i){
            s.push(putIn[i]);
            while(!s.empty() && s.top() == takeOut[k]){
                s.pop();
                ++k;
            }
        }
        return s.empty();
    }
};

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

0 赞同 0 条回复

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

共以下 42 个回答

# 回答此问题取消回复

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

共以下 42 个回答

# 回答此问题 取消回复

# 回答此问题取消回复