数据结构学习 jz31 栈的压入、弹出序列

关键词：模拟 栈

不太熟，调了好一阵子。

题目：https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/

?

思路：

主要是利用一个辅助栈，来模拟这个过程，如果过程不行就返回失败。

int sig = 0;如果这一轮没有任何操作，说明卡住了，返回false

int put = 0;记录推入的次数

int pop = 0;记录推出的次数

一直推入，直到和要推出的第一个数相同。

            while (put < putIn.size())
            {

                sk.push(putIn[put]);
                put++;//指向下一个准备被推入的数
                sig = 1;
                if (sk.top() == takeOut[pop])
                    break;
            }

?一直推出，直到和辅助栈栈顶元素不一样。

如果所有都推出了pop == takeOut.size()，则说明成功，返回true。

            while (pop < takeOut.size() && !sk.empty() && sk.top() == takeOut[pop])
            {
                sk.pop();
                pop++;//指向下一个准备被推出的数
                sig = 1;
                if (pop == takeOut.size())
                    return true;
            }

复杂度计算：

时间复杂度O(n) 2n进进出出

空间复杂度O(n) 辅助栈?

代码：

class Solution {
public:
    bool validateBookSequences(std::vector<int>& putIn, std::vector<int>& takeOut) {
        if (takeOut.empty()) return true;
        std::stack<int> sk;
        int put = 0;
        int pop = 0;
        while (true)
        {
            int sig = 0;
            while (put < putIn.size())
            {

                sk.push(putIn[put]);
                put++;//指向下一个准备被推入的数
                sig = 1;
                if (sk.top() == takeOut[pop])
                    break;
            }
            while (pop < takeOut.size() && !sk.empty() && sk.top() == takeOut[pop])
            {
                sk.pop();
                pop++;//指向下一个准备被推出的数
                sig = 1;
                if (pop == takeOut.size())
                    return true;
            }
            if (sig == 0)
                return false;
        }
    }
};

k神答案：非常简洁，建议学习

class Solution {
public:
    bool validateBookSequences(vector<int>& putIn, vector<int>& takeOut) {
        stack<int> stk;
        int i = 0;
        for(int num : putIn) {
            stk.push(num); // num 入栈
            while(!stk.empty() && stk.top() == takeOut[i]) { // 循环判断与出栈
                stk.pop();
                i++;
            }
        }
        return stk.empty();//因为最后结果是所有数都要出栈，所以stk如果还有数就说明失败
    }
};