42. 栈的压入、弹出序列
题目描述
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。
假设压入栈的所有数字均不相等。
例如序列 1,2,3,4,5 是某栈的压入顺序,序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列,但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。
注意:若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空,则视为是一个栈的压入、弹出序列。
数据范围
序列长度 [0,1000]。
样例
输入:[1,2,3,4,5]
[4,5,3,2,1]
输出:true
算法1 用辅助栈模拟输出过程
算法流程
整个操作过程是唯一的,没有变数,不存在多种情况或选择,所以直接模拟就行
存在两种操作,每次只能进行其中一个
1. 将下一个数加入栈中
2. 将当前栈顶元素弹出
判断当前栈顶元素是否和下一个要输出的数是一样的
1)一样:必然将当前栈顶元素弹出,否则压入的话,在输出当前数之前还会输出别的数,就不匹配了
2)不一样:必然会将输入序列的下一个元素加入栈中,否则输出直接不匹配
时间复杂度 $O(n)$
每个元素需要入栈1次,出栈一次
总共入栈n次,出栈n次
C++ 代码
class Solution {
public:
bool isPopOrder(vector<int> pushV,vector<int> popV) {
if(pushV.size() != popV.size()) return false;
stack<int> stk; //用栈模拟得到序列的整个过程
int i = 0;
for(auto x : pushV) //保证输入序列每个元素入栈
{
stk.push(x); //保证开始的时候栈中存在元素
//循环判断当前栈顶元素是否匹配输出
//while作用:将目前所有匹配的都弹出,否则当前数需等后续弹出才能弹出
while(stk.size() && stk.top() == popV[i])
{
stk.pop();
i++;
}
}
return stk.empty();
}
};