目录
1.题目描述
2.题解
方法1
方法2
1.题目描述
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。
1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. pushV 的所有数字均不相同
示例:
输入:[1,2,3,4,5],[4,5,3,2,1]
返回:true
输入:[1,2,3,4,5],[4,3,5,1,2]
返回:false
2.题解
方法1
思路分析:
判断两个序列是否符合入栈、出栈的次序,我们可以使用一个栈来模拟。
入栈:栈顶元素不等于出栈序列当前元素
出栈:栈顶元素等于出栈序列当前元素
具体过程:
具体实现:
1.创建一个栈,来模拟入栈、出栈次序
2.使用i、j来遍历pushV、popV数组,i < pushV.length,入栈
3.栈顶元素等于popV数组当前元素时,出栈
4.遍历完pushV数组后,判断栈是否为空,栈为空,弹出序列为正确的出栈顺序;反之,则为错误的出栈顺序
代码实现:
public class Solution {
public boolean IsPopOrder (int[] pushV, int[] popV) {
Stack<Integer> stack = new Stack<>();
int j = 0;
for (int i = 0; i < pushV.length; i++) {
stack.push(pushV[i]);
//判断是否有元素出栈
while(j < popV.length && !stack.empty()){
int k = stack.peek();
if(k == popV[j]){
stack.pop();
j++;
}else{
break;
}
}
}
return stack.empty();
}
}
方法2
思路分析:
由于数组本身就可用于实现栈,我们可以将pushV数组当作栈,使用p来标记栈顶,
入栈:pushV[p](栈顶元素)不等于当前出栈数组中元素,p++(入栈)
出栈:pushV[p](栈顶元素)等于当前出栈数组中元素,p--(出栈)
具体过程:
具体实现:
1.使用p来标识栈顶元素
2.使用i、j来遍历pushV、popV数组,pushV[p](栈顶元素)不等于当前出栈数组中元素,
pushV[p] = pushV[i],p++
3.pushV[p](栈顶元素)等于当前出栈数组中元素,p--
4.遍历完pushV数组后,判断p的大小,若p为0,则表示所有元素都已出栈,出栈序列为正确的出栈顺序,返回true,否则,返回false
代码实现:
public class Solution {
public boolean IsPopOrder (int[] pushV, int[] popV) {
int p = 0;//标识栈顶
int j = 0;//出栈序列下标
for(int n : pushV){
pushV[p] = n;
while( p>=0 && j < popV.length && pushV[p] == popV[j]){
j++;
p--;
}
p++;
}
return p==0;
}
}
题目来自:文章来源:https://www.uudwc.com/A/R62mo/
栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)文章来源地址https://www.uudwc.com/A/R62mo/