剑指offer-栈的压入、弹出序列

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

解题思路

考虑用i、j分别记录栈的压入顺序和弹出顺序，当遇到栈顶元素和当前弹出序列第j个数相等时，那就把栈顶元素弹出并且令j=j+1；当遇到栈为空或者栈顶元素和当前弹出序列第j个数不相等时，那就把当前栈的压入顺序中第i个数入栈，并令i=i+1。如果遇到压入序列为空并且栈顶元素和当前弹出序列第j个数不相等，说明该序列不可能是该压栈序列的弹出序列。

代码

 1 class Solution {
 2 public:
 3     bool IsPopOrder(vector<int> pushV,vector<int> popV) {
 4         bool isPop=true;
 5         stack<int> s;
 6         int i=0,j=0;
 7         while(j<popV.size()){
 8             if(s.size()&&s.top()==popV[j]){
 9                 j++;
10                 s.pop();
11             }
12             else{
13                 if(i<pushV.size())
14                     s.push(pushV[i++]);
15                 else{
16                     isPop=false;
17                     break;
18                 }
19             }
20         }
21         return isPop;
22     }
23 };