剑指offer——面试题22：栈的压入、弹出序列

Solution1:

要理解并背诵此题！

参考网址：

思路：

1.建立一个辅助栈；

2.将第一个序列的数字压入辅助栈；

3.如果第二个序列的下一个弹出数字刚好是栈顶数字，则直接弹出，第二个序列弹出当前数字，辅助栈也弹出该数字；

4.否则，就把第一个序列中尚未入栈的数字压入辅助栈，直到把第二个序列中下一个需要弹出的数字压入栈顶为止。

5.如果第一个序列的所有数字都已经入栈了，第二个序列中仍然有数字未被弹出，即辅助栈未被清空。则return false。

class Solution {public:    bool IsPopOrder(vector
   
     pushV,vector
    
      popV) {        if(pushV.size() == 0) return false;        vector
     
       stack;        for(int i = 0,j = 0 ;i < pushV.size();){            stack.push_back(pushV[i++]);            while(j < popV.size() && stack.back() == popV[j]){                stack.pop_back();                j++;            }              }        return stack.empty();    }};

Solution2:

20180901重做

class Solution {public:    bool IsPopOrder(vector
   
     pushV,vector
    
      popV) {        if (pushV.size() == 0) return false;        stack
     
       push_stack;        for (int i = 0,j = 0 ;i < pushV.size();) {            push_stack.push(pushV[i++]);            while (j < popV.size() && push_stack.top() == popV[j]) {                push_stack.pop();                j++;            }        }        return push_stack.empty();    }};

转载地址：http://fxhdb.baihongyu.com/

你可能感兴趣的文章