题解 | #栈的压入、弹出序列#
栈的压入、弹出序列
http://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106
思路:
第一想法就是:依次从左往右遍历两个数组来维护一个栈;
- 遍历入栈数组时判断当前元素值是否等于出栈元素当前值:
- 若相等则栈出栈,并且两个数组均向右移动到下一个元素;
- 若不相等则栈入栈当前入栈数组元素,入栈数组向右移动到下一个元素;
- 这样就模拟出了栈出入栈的过程,当遍历结束后,只要判断维护的栈是否是空的即可得到结果。
代码如下:
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
int psz=pushV.size();
int posz=popV.size();
if(psz==0 && posz==0) return true;//若两个数组均为空返回true
if(psz==0 || posz==0) return false;//若只有其中一个数组为空,则返回false
stack<int> stk1;//维护一个栈
int i=0;int j=0;
while(i<psz && j<posz){//遍历终点时遍历完两个数组中的其中一个即可
while(i<psz && (stk1.empty() || stk1.top()!=popV[j])){ // 入栈
//遍历时条件判断从左至右依次是数组下标不越界、栈为空时、栈不为空且栈顶元素不等于当前出栈元素时
stk1.push(pushV[i++]);//入栈后下标右移
}
while(j<posz && !stk1.empty() && stk1.top()==popV[j]){ // 出栈
//遍历时条件判断从左至右依次是数组下标不越界、栈不为空时、栈顶元素等于当前出栈元素
stk1.pop(); //出栈
j++; // 下标右移
}
}
return stk1.empty(); //返回最后维护的栈是否为空即可
}
};
- 时间复杂度: 因为要遍历完两个数组所有元素,所以时间复杂度为O(N+N),即O(N);
- 空间复杂度: 维护了一个栈,最大消耗空间为N个元素占用空间,因此空间复杂度为O(N)