栈的压入、弹出序列
2023-04-18 12:56:40 时间
题目描述
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
例如序列 1,2,3,4,5 是某栈的压入顺序,序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列,但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。
解题思路
使用一个栈来模拟压入弹出操作。每次入栈一个元素后,都要判断一下栈顶元素是不是当前出栈序列 popSequence 的第一个元素,如果是的话则执行出栈操作并将 popSequence 往后移一位,继续进行判断。如果最后栈中还有元素存在,说明有不相等的序列存在,那么就不是该压栈序列的弹出序列。
public boolean IsPopOrder(int[] pushSequence, int[] popSequence) {
int n = pushSequence.length;
Stack<Integer> stack = new Stack<>();
for (int pushIndex = 0, popIndex = 0; pushIndex < n; pushIndex++) {
stack.push(pushSequence[pushIndex]);
while (popIndex < n && !stack.isEmpty()
&& stack.peek() == popSequence[popIndex]) {
stack.pop();
popIndex++;
}
}
return stack.isEmpty();
}
相关文章
- iPhone XR销量不佳,苹果用以旧换新大幅打折促销
- 90%的设计师都认同这7个设计习惯,然而它们可能会害了你
- 一文读懂AI专核的“身份”
- 谷歌正测试新操作系统Fuchsia 有望在今年取代安卓
- 谷歌虚拟移动服务Fi将支持iPhone、三星、一加
- 后台系统的「权限设计」基础知识科普
- 全球最大安卓第三方系统LineageOS宣布:放弃对30个机型的维护
- 小米、华为、OPPO“打群架”,锤子、魅族难“求生”
- 苹果重启iPhone X的生产,或许不是一个好主意
- 基础知识!UI设计师需要掌握的栅格设计原理和技巧
- 订单削减 股价大跌 苹果策略调整的这个冬天
- 你可曾想过在iOS上跑Linux?
- 安卓9.0升级太慢,谷歌想让用户直接测试 Android Q
- 智能手机市场饱和,未来什么功能能让你甘心掏钱
- Android App的设计架构MVC MVP MVVM与架构经验谈
- 故意让手机变慢!苹果三星被罚巨款
- iOS应用程序的脱壳实现原理浅析
- 安卓系统收费标准出炉,谷歌“敛财之手”会伸进国产厂商腰包吗?
- Path、Google+和子弹短信,社交产品的第二名没有意义
- 关于iPad版Photoshop CC 你想知道的细节