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

LovLe 普通 2024年12月18日上午6:42

class Solution:
    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:
        stack=[]
        for i in range(len(putIn)):
            if not stack or takeOut[0]!=stack[-1]:
                stack.append(putIn[i])
            while takeOut and stack and takeOut[0]==stack[-1]:  # 当两者都有数据时，才可以比较。而且一直比较模拟栈栈顶元素是否可以在当下被取出（while），takeOut顺序中值不重复。如何判断这就是跳出这个while，当已经遍历完putIn后，就是最后的状态：极端状态，如果模拟栈一直没有pop，一直添加完putIn，那么就会while一直和takeOut顺序元素比较pop stack[-1]栈顶元素，如果stack为空了，那么就说明都pop完了，顺序是对的，此时takeOut也遍历完了。
                stack.pop()
                takeOut.pop(0)
        if stack:   # 如果模拟栈中还有数据，那么不对，说明顺序有误，不然就已经pop清空了。takeOut也不为空
            return False
        else: 
            return True

0 赞同 0 条回复

yelinliner 普通 2024年12月4日下午9:36

###

class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        if (putIn == null || putIn.length <= 0) {
            return true;
        }
        // 辅助栈
        Stack<Integer> temp = new Stack<Integer>();
        int k = 0;
        for (int i = 0; i < putIn.length; i++) {
            temp.push(putIn[i]);
            // 说明遇到出栈操作
            while (!temp.isEmpty() && takeOut[k] == temp.peek()) {
                temp.pop();
                k++;
            }
        }
        return temp.isEmpty();
    }
}

0 赞同 0 条回复

岱永久会员 2024年12月3日下午3:38

循环判断

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

陆狗陆狗普通 2024年11月30日下午9:55

【不建议】题解：按取出的数组先遍历，只要取出的值在栈中不存在，就去入栈数据遍历进行放入。

class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        // 后面只需要考虑putIn和takeOut都不为0的情况了
        // putIn一定是按照顺序的，只需要考虑takeOut是否按照顺序的即可，所以去遍历takeOut
        // 【错误点，栈和队列搞反了】
        Stack<Integer> queue = new Stack<>();
        int inLength = 0;
        for (int i = 0; i < takeOut.length; i++) {
            int taretValue = takeOut[i];
            if (queue.isEmpty() || taretValue != queue.peek()) {
                // 已经把putIn数组的数据全部都放到队列里面了,队列第一个元素不是目标元素，说明顺序错误
                while (inLength < putIn.length) {
                    // 放入数据到队列中
                    int offerValue = putIn[inLength++];
                    queue.push(offerValue);
                    // 如果刚放入队列的数据就是目标要取出的数据，不继续放入了
                    if (offerValue == taretValue) {
                        break;
                    }
                }
                if (queue.peek() == taretValue) {
                    queue.pop();
                } else {
                    return false;
                }
            } else {
                queue.pop();
            }
        }
        return true;
    }
}

错误点1：栈和队列的性质搞反了

【建议】改进：按照putIn进行遍历数据加入栈，如果栈顶数据能够被take出来，最后判断栈是否为空即可。
好处是，遍历putIn可以把元素放到栈里面暂存，代码能够写的更加讲解一些

class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        // 后面只需要考虑putIn和takeOut都不为0的情况了
        // putIn之后，只要发现栈顶数据能被takeOut就拿出，最后判断栈是否为空即可
        Stack<Integer> stack = new Stack<>();
        int j=0;
        for (int i = 0; i < putIn.length; i++) {
            stack.push(putIn[i]);
            // 栈顶数据能被takeOut就拿出
            while(!stack.isEmpty() && stack.peek()==takeOut[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日下午8:05

/**
解题思路：模拟
依次遍历pushed入栈，如果栈顶与popped[j]相同，则出栈并继续比较，最终栈元素全部弹出则序列有效
时间复杂度O(N),空间复杂度O(N)
 */
class Solution {
    public boolean validateBookSequences(int[] pushed, int[] popped) {

        Deque<Integer> st = new ArrayDeque<>();
        int j = 0;
        for (int i = 0; i < pushed.length; i++){
            st.add(pushed[i]);
            while (!st.isEmpty() && st.getLast() == popped[j]){
                j++;
                st.pollLast();
            }
        }
        return st.isEmpty();

    }
}

0 赞同 0 条回复

Firefly 普通 2024年11月30日下午4:27

class Solution {
public:
bool validateBookSequences(vector& putIn, vector& takeOut) {
std::stack m_sk;//辅助栈
auto i=0,j=0;
while(i<takeOut.size())
{
if(m_sk.empty()||m_sk.top()!=takeOut[i]&&j<putIn.size())
{
while(j<putIn.size())
{
if(putIn[j]!=takeOut[i])
{
m_sk.push(putIn[j++]);

                }
                else
                {
                    i++,j++;
                    break; 
                }
            } 
        }
        else
        {
            if(m_sk.top()!=takeOut[i])
                break;
            m_sk.pop();
            i++;
        }
    }
    return m_sk.size()==0;
}

};
//使用辅助栈

0 赞同 0 条回复

Tom Yuan 普通 2024年11月27日下午6:06

思路用一个stack模拟然后用贪心的想法把能按顺序pop的都pop了如果能pop完就说明可以

class Solution:
    def validateBookSequences(self, putIn: List[int], takeOut: List[int]) -> bool:
        simu_stack = []
        pop_count = 0
        for num in putIn:
            simu_stack.append(num)
            while simu_stack and pop_count < len(takeOut) and simu_stack[-1] == takeOut[pop_count]:
                # try to pop all that equals
                simu_stack.pop()
                pop_count += 1
        return not len(simu_stack)

space O(n) time O(n)

0 赞同 0 条回复

生活在经验里普通 2024年11月27日下午3:03

// 辅助栈, 模拟 压入 / 弹出操作的排列
func validateStackSequences(pushed []int, popped []int) bool {
    stack := make([]int, 0)
    j := 0
    for _, push := range pushed {
        stack = append(stack, push)
        //辅助栈不为空且栈顶元素与 popped 的当前元素相同，则将栈顶元素出栈
        for len(stack) > 0 && stack[len(stack)-1] == popped[j] {
            stack = stack[:len(stack)-1]
            j++
        }
    }
    return len(stack) == 0
}

0 赞同 0 条回复

越努力越幸运普通 2024年11月26日下午11:57

以前选择题经常这么考

class Solution {
public:
    bool validateBookSequences(vector<int>& putIn, vector<int>& takeOut) {
        if(putIn.empty())
        {
            return true;
        }
        int k = 0;
        stack<int> s;
        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();
    } 
};

0 赞同 0 条回复

Jerry 普通 2024年11月26日下午4:00

class Solution {
public:
    bool validateBookSequences(vector<int>& putIn, vector<int>& takeOut) {
        stack<int> stk;
        int targetindex = 0;
        for(int i = 0; i < putIn.size() && targetindex < takeOut.size(); i++){
            stk.push(putIn[i]);
            while(!stk.empty() && stk.top() == takeOut[targetindex]){
                targetindex++;
                stk.pop();
            }
        }
        if(stk.empty()){
            return true;
        }
        return false;
    }
};

思路：
（1）将takeout中的元素依次作为target目标值；
（2）将putin元素按顺序压入栈中，直至栈顶元素和target相等（这时候才能取出目标值）：目标值后移+删除栈顶元素（循环至栈顶元素！=目标值）。
如果最后栈空，说明能够按照takeout的顺序读取元素。
时间：o(n)
空间：o(n)

0 赞同 0 条回复

mpweixin用户普通 2024年11月25日下午10:33

class Solution {
public:
    bool validateBookSequences(vector<int>& putIn, vector<int>& takeOut) {
        if(putIn.size() != takeOut.size()){
            return false;
        }
        if(putIn.empty()){
            return true;
        }
        int j = 0;
        stack<int> s;
        for(int i = 0; i<putIn.size();i++){
            s.push(putIn[i]);
            while(j<takeOut.size() && !s.empty() && s.top() == takeOut[j]){
                j++;
                s.pop();
            }
        }
        return s.empty();
    }
};

思路：设一个栈模拟，按入栈数组顺序依次入栈，每次加入新元素后都与当前指向出栈数组的元素判断，相同则弹出栈，直到不同为止再新加入元素。最后，如果栈内没有元素存在，则意味着顺序是正确的，反之则序列不成立
时间O(N),空间O(N)

0 赞同 0 条回复

lQl 永久会员 2024年11月25日下午10:04

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

class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        int i =0;
        int j = 0;
        int m = putIn.length;
        Stack<Integer> s = new Stack<>();
        int cnt = 0;
        while(i<m){
            if(i<m){
                s.push(putIn[i]);
                i++;
            }
            while(!s.empty()&&s.peek()==takeOut[j]){
                s.pop();
                j++;
            }
        }
        return s.empty();
    }
}

0 赞同 0 条回复

张君雅小妹妹普通 2024年11月25日下午9:34

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

        if(stack.isEmpty()){
            return true;
        } else {
            return false;
        }
    }
}

思路是对的，但是少了stack为empty的边界值判断
时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

秋山丽奈普通 2024年11月25日下午8:12

思路：根据两个序列进行出入栈操作，若最后栈空说明有效

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

Pendulumpal 普通 2024年11月25日下午5:57

模拟栈操作

“`c++
bool validateBookSequences(vector& putIn, vector& takeOut) {
stacksk;
int len=putIn.size();
int inid=0,outid=0;
while(outid=len&&sk.size())return false;
}
return true;
}
“`

0 赞同 0 条回复

Kisara 普通 2024年11月25日下午4:44

用一个栈模拟存取操作，模拟成功就返回true 失败就返回false

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

        return stack.isEmpty();
    }
}
O（N）时间  O（n）空间

0 赞同 0 条回复

无言永久会员 2024年11月25日下午3:10

class Solution {
public:
    bool validateBookSequences(vector<int>& putIn, vector<int>& takeOut) {
        stack<int> stk;
        int index = 0; 
        for(int x : putIn) {
            stk.push(x);
            while(!stk.empty() && takeOut[index] == stk.top()){
                // 书籍被拿取，则出栈
                stk.pop();
                index++;
            }
        }
        if(stk.empty()) // 如果 takeOut 按照正确的顺序拿取书籍，最后栈会为空
            return true;
        return false;
    }
};
时间复杂度 O(N)
空间复杂度 O(N)

0 赞同 0 条回复

苯庸普通 2024年11月25日下午2:55

class Solution {
public boolean validateBookSequences(int[] putIn, int[] takeOut) {
Stack st = new Stack();
int j = 0;
for(int x : putIn){
st.push(x);
while(j < takeOut.length && !st.isEmpty() && st.peek() takeOut[j]){
st.pop();
j++;
}
}
return j takeOut.length;
}
}
时间：O（n）
空间：O（n）

0 赞同 0 条回复

月下足迹普通 2024年11月25日下午2:14

class Solution {
public boolean validateBookSequences(int[] putIn, int[] takeOut) {
int p1 = 0; //putin栈指针
int index = 0; // 用于指向 takeOut 数组中的元素

        for (int i = 0; i < takeOut.length; i++) {
            putIn[p1] = putIn[i];
            p1++;

            while (p1>0 && putIn[p1-1] == takeOut[index]) {
                p1--;
                index++;
            }
        }

        return p1 == 0;
}

}

0 赞同 0 条回复

黑键〰普通 2024年11月25日下午12:54

/**
 * @param {number[]} putIn
 * @param {number[]} takeOut
 * @return {boolean}
 */
var validateBookSequences = function(putIn, takeOut) {
    if(!putIn.length) return true
    let stack = []
    let p = 0
    for(let i=0; i<putIn.length; i++) {
        stack.push(putIn[i])
        // 辅助栈栈顶和取出栈比较
        while(stack.length > 0 && stack.slice(-1)[0] == takeOut[p]) {
            stack.pop()
            p++
        }
    }
    return stack.length == 0
};

思路：画图辅助确实可以帮助理解更快并且思路也更清晰，返回检查的时候也能快速推导。时间空间复杂度都是O(N)，因为要遍历，还有辅助栈存储

0 赞同 0 条回复

Renasc 普通 2024年11月25日上午11:02

时间复杂度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]) {  // 如果当前入栈的元素等于takeOut[i]就直接出栈
                stack.pop();
                i++;
            }
        }
        // 如果最后栈为空，说明putIn中所有元素 都可以通过takeOut的顺序来获取
        return stack.isEmpty();
    }
}

0 赞同 0 条回复

Xiang. 永久会员 2024年11月25日上午10:55

思路：直接进行一波出栈模拟，如果最后栈为空，则表示成功
class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        Stack<Integer> A=new Stack();
        int num=0;
        for(int i:putIn){
            A.push(i);
            while(!A.isEmpty()&&A.peek()==takeOut[num]){
                A.pop();
                num++;
            }
        }
         return A.isEmpty();
    }
}
时间空间复杂度均为O(n)

0 赞同 0 条回复

youngsir 普通 2024年11月25日上午9:22

打卡

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

    }
};

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

0 赞同 0 条回复

jaron 普通 2024年11月24日下午10:50

时间复杂度：O(n) 遍历了一遍数组
额外空间复杂度：O(n)

class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        if (putIn == null || putIn.length == 0) {
            return true;
        }
        Stack<Integer> stack = new Stack();
        for (int i = 0, j = 0; i < putIn.length; i++) {
            // 先从 putIn 放入栈
            stack.push(putIn[i]);
            // 循环判断是否能出栈
            while (!stack.isEmpty() && stack.peek() == takeOut[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}

0 赞同 0 条回复

🍊 普通 2024年11月24日下午10:05

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

0 赞同 0 条回复

晓宇普通 2024年11月24日下午8:44

···cpp
class Solution {
public:
bool validateBookSequences(vector& putIn, vector& takeOut) {
if(putIn.empty()) return true;
stack s;
int cnt_o = 0;
for(int i = 0;i < putIn.size();i ++){
s.push(putIn[i]);
while(!s.empty() && s.top() takeOut[cnt_o]){
s.pop();
cnt_o++;
}
}
return s.empty();
}
};
// 思路：利用栈先入后出的性质
// 时间复杂度 o(n) 空间复杂度 o(n)

“`

0 赞同 0 条回复

迢迢星野普通 2024年11月24日下午7:49

class Solution {
    public boolean validateBookSequences(int[] putIn, int[] takeOut) {
        // 栈操作
        Stack<Integer> stack = new Stack<>();
        // 出栈：按照 takeOut 的顺序进行出栈
        int idx = 0;
        for (int i = 0; i < putIn.length; i++) {
            // 入栈：按照 putIn 的顺序进行入栈
            stack.push(putIn[i]);
            // 什么时候出栈？栈不为空，且栈顶元素与 takeOut 对应的元素相等时出栈
            while (!stack.empty() && takeOut[idx] == stack.peek()) {
                idx++;
                stack.pop();
            }
        }
        // 若栈为空，则说明出栈成功
        return stack.empty();        
    }
}

思路：通过栈来模拟书架的操作，确保每次出栈顺序与 takeOut 数组一致。
时间复杂度：O(n)，遍历了 putIn 数组。
空间复杂度：O(n)，使用了栈，元素个数为 n。

0 赞同 0 条回复

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

共以下 27 个回答

# 回答此问题取消回复

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

共以下 27 个回答

# 回答此问题 取消回复

# 回答此问题取消回复