《剑指offer刷题笔记》30、栈的压入、弹出序列【c++详细题解】

Myth丶恋晨 2021-07-24 20:58 179阅读 0赞

### **题目** ###

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

假设压入栈的所有数字均不相等。

例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1是该压栈序列对应的一个弹出序列，但 4,3,5,1,2就不可能是该压栈序列的弹出序列。

**注意**：若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空，则视为是一个栈的压入、弹出序列。

**样例**

输入：[1,2,3,4,5]
          [4,5,3,2,1]
    
    输出：true

### **思路** ###

**(模拟 )** O ( n ) O(n) O(n)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]  
我们定义一个空栈`st`，然后模拟这个过程。

假设我们已经处理了出栈序列中的前`i-1`个数，现在要让`popV[i]`出栈。如果`popV[i]`不在栈中，我们就要将入栈序列`pushV[i]`中的若干个数压进栈中，直到`popV[i]`入栈。

*  如果当前要出栈的`popV[i]`元素在栈首，那么我们将其弹出。
 *  如果当前要出栈的`popV[i]`元素不在栈首，那么原问题无解。

最后判断`st`中元素是否为空，为空则表示当前出栈序列可取。

**时间复杂度分析**

遍历整个出栈序列的时间复杂度为 O ( n ) O(n) O(n),`while`循环最多执行`n`次，因此总的时间复杂度为 O ( n ) O(n) O(n)

### **代码** ###

class Solution { 
    public:
        bool isPopOrder(vector<int> pushV,vector<int> popV) { 
            if(pushV.size()!=popV.size()) return false; //两个序列长度不等，直接返回false
            stack<int>st;
            int k  = 0;
            for(int i = 0; i < popV.size(); i++)
            { 
                while(st.empty()||popV[i] != st.top()) st.push(pushV[k++]);
                if(st.top() == popV[i]) st.pop();
                else return false;
            }
            return st.empty();
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/5b10d095df65447fa05f779dc77b71c7.png