18，输入两个序列一个代表入栈顺序，验证另一个是否是出栈序列《剑指offer》...

100 阅读 0 评论 66 点赞

我是靠谱客的博主勤奋豌豆，这篇文章主要介绍18，输入两个序列一个代表入栈顺序，验证另一个是否是出栈序列《剑指offer》...，现在分享给大家，希望可以做个参考。

题目：

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

思路：

需要用到两个指针和一个辅助栈：

popIndex指向出栈的元素

pushIndex指向入栈的元素

mStack作为辅助栈根据压栈序列和出栈序列模拟原始操作

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
if(pushV.size()!=popV.size()||pushV.size()==0) return false;
int pushIndex=0; //指向入栈的元素
int popIndex=0; //指向需要出栈的元素
stack<int> mStack;
while(popIndex<popV.size()){
while(mStack.empty()||mStack.top()!=popV[popIndex]){ //当栈为空 或者 栈顶元素不等于该出栈的元素 执行入栈操作
if(pushIndex==pushV.size()) break;
//全部入栈
mStack.push(pushV[pushIndex]);
pushIndex++;
}
if(mStack.top()!=popV[popIndex]){ //两种可能 1,全部入栈 2，栈顶元素等于出栈元素
return false;
//全部入栈，栈顶元素不等于出栈的元素，就证明不是出栈序列
}
mStack.pop();
popIndex++;
}
return true;
}
};