题目要求:
解题思路:
用一个栈模拟入栈,出栈的顺序,如果最后能够将栈中元素全部弹出,那么就存在此出栈序列,否则便是没有.
具体伪代码如下:
func(){
初始化一个栈
while(入栈序列不为空){
元素入栈
while(栈顶元素等于当前出栈元素){
出栈
当前要出栈的元素变为为下一个元素
}
}
}
具体C++代码如下:
class Solution {
public:
bool validateStackSequences(vector& pushed, vector& popped) {
// 对于入栈序列中的每一个元素,当栈顶元素不等于当前要出栈的元素时候,那么就入栈,一直到等于当前出栈序列的元素出现,然后入栈,出栈,一直循环上述操作直到需要入栈的元素全部入栈,如果此时栈不为空,则此出栈序列不是该整数序列的出栈序列.否则就是.
stacks;
for(int i=0,j=0;i
时间复杂度和空间复杂度分析:
由于需要遍历入栈序列和出栈序列,共2N个元素,因此时间复杂度为O(2N)
由于需要一个长度最大为N的辅助栈,因此空间复杂度为O(N)
