淘宝网站建设方案模板,qq官网登录入口电脑版,手机网站展示,php网站开发发展趋势目录
1.题目描述
2.题解
方法1
方法2 1.题目描述
输入两个整数序列#xff0c;第一个序列表示栈的压入顺序#xff0c;请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序#xff0c;序列4,5,3,2,1是该压栈序…目录
1.题目描述
2.题解
方法1
方法2 1.题目描述
输入两个整数序列第一个序列表示栈的压入顺序请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序序列4,5,3,2,1是该压栈序列对应的一个弹出序列但4,3,5,1,2就不可能是该压栈序列的弹出序列。 1. 0pushV.length popV.length 1000 2. -1000pushV[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) {StackInteger 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( p0 j popV.length pushV[p] popV[j]){j;p--;}p;}return p0;}
}
题目来自
栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)
