JZ-021-栈的压入、弹出序列
2024-10-18 10:16:43
栈的压入、弹出序列
题目描述
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
- 例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。
- (注意:这两个序列的长度是相等的)
题目链接: 栈的压入、弹出序列
代码
import java.util.Stack;
/**
* 标题:栈的压入、弹出序列
* 题目描述
* 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
* 例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。
* (注意:这两个序列的长度是相等的)
* 题目链接:
* https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
*/
public class Jz21 {
public boolean isPopOrder(int[] pushA, int[] popA) {
int n = pushA.length;
Stack<Integer> stack = new Stack<Integer>();
for (int pushIndex = 0, popIndex = 0; pushIndex < n; pushIndex++) {
stack.push(pushA[pushIndex]);
while (popIndex < n && !stack.isEmpty() && stack.peek() == popA[popIndex]) {
stack.pop();
popIndex++;
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
int[] pushA = new int[]{1, 2, 3, 4, 5};
int[] popA = new int[]{4, 5, 3, 2, 1};
int[] popB = new int[]{4, 3, 5, 1, 2};
Jz21 jz21 = new Jz21();
System.out.println(jz21.isPopOrder(pushA, popA));
System.out.println(jz21.isPopOrder(pushA, popB));
}
}
【每日寄语】 前路浩浩荡荡,万事尽可期待。
最新文章
- discuz上传图片提示附件文件无法保存
- log4j向oracle中插入一条系统当前时间的sql语句
- 【Android】[转] ANR的分析和问题处理
- UIApplication和delegate代理
- 【python cookbook】【字符串与文本】1.针对任意多的分隔符拆分字符串
- [转]将Word转(保存)为带书签的PDF
- attachEvent和addEventListener详解
- Android面试经验1
- perl-5.14.0在新版gcc中编译不通过解决办法
- 小程序中曾经遇到的坑(1)----canvas画布
- 【BZOJ1010】【HNOI2008】玩具装箱(斜率优化,动态规划)
- Java面向对象--类的对象之间的几种关系详解
- 利用pyinstaller生成exe之后,运行不能正常产生结果文件问题记录
- git push 和 pull 时 免密执行的方法
- 用winhotkey添加属于自己的快捷键
- Python 字典 fromkeys()方法
- linux 查看、关闭 ssh pts/n登录的用户
- .NetCore Cap 注册 Consul 服务发现
- bzoj4161: Shlw loves matrixI
- bzoj千题计划114:bzoj1791: [Ioi2008]Island 岛屿