描述
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。
假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。
- 0<=pushV.length == popV.length <=1000
- -1000<=pushV[i]<=1000
- pushV 的所有数字均不相同
思路1:模拟栈操作
空间复杂度O(n)
序列1:{1,2,3,4,5},i
序列2:{4,3,5,2,1},j
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
Stack<Integer> stack = new Stack<>();
int j = 0;
//直到序列1压完了
for(int e: pushA) {
//push[i] != pop[j],压栈
stack.push(e);
//pop[j]和栈顶比较,如果相等,则pop
while(!stack.isEmpty() && stack.peek() == popA[j]) {
stack.pop();
j++;;
}
}
//判断元素是否全部出栈
return stack.isEmpty();
思路2:使用size代替栈
可以直接在序列1上操作,空间复杂度O(1)
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
int size = 0;
int j = 0;
for(int e: pushA) {
//入栈
pushA[size] = e;
while(size >= 0 && pushA[size] == popA[j]) {
//出栈
size--;
j++;
}
size++;
}
return size == 0;
}
}