剑指offer-21-栈的压入、弹出序列

栈的压入、弹出序列_牛客网

https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&tqId=11174&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

思路比较简单,但是不知道为什自己写起来代码怎么这么难看,一点都不简洁。
思路:按照入栈的顺序重新入栈一次,但是在入栈的时候,要结合出栈的顺序来判断是否应该出栈。比如将1加入栈中时,发现出栈的第一个元素为4,不等于1,因此就直接入栈,知道将4加入栈中的时候,因为为出栈的第一个元素,因此要执行一个pop操作。

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        int len = pushA.length;
        Stack<Integer> s = new Stack<Integer>();
        int i = 0;
        int j = 0;;
        for(; j<len && i < len; ){
            while(i < len && pushA[i] != popA[j]){
                s.p

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

小白刷剑指offer 文章被收录于专栏

跟着小白一起刷剑指offer,通过讨论加深印象吧~ 没有人不学习就能够掌握知识,知识就是需要学习的~

全部评论
楼主 ,第二个代码如果是与遇到12345和12345这种情况,压入1的时候,进入while循环,第一次循环会弹出1,第二次循环peek方法是不是就会报空栈异常呢? 感觉你的代码好像只适合第5次弹栈才能弹空,前面弹空就会报错,while循环就会出错
1 回复 分享
发布于 2020-05-11 19:17
第二个代码第10行改为 while(s.peek() == popA[j] && j < len) 就通不过,显示你的输出为: java.util.EmptyStackException 谁能告诉我为什么。。。
1 回复 分享
发布于 2020-02-10 02:35
第10行的while循环少了个条件,因为像上面楼主说的,如果栈空了while条件里的stack.peek()就会报异常,所以可以修改为: while(j < len && !stack.isEmpty() && stack.peek() == popA[j]){ //...}
点赞 回复 分享
发布于 2021-06-07 19:38
这题有点水平,我不信怎么才给了一星的难度
点赞 回复 分享
发布于 2021-03-05 20:45
第二个代码中,首先应该判断pushA和popA的长度是否相同。如果是相同的这个代码没问题,如果是不想相同的可能就有点问题了。比如:int[] pushA={1,2,3,4,5};int[] popA={4,5,3,2,1,2}; 但是题目有(注意:这两个序列的长度是相等的),所以这道题没问题。
点赞 回复 分享
发布于 2019-11-27 19:03

相关推荐

AAA专业长城贴瓷砖刘大爷:这样的简历我会直接丢进垃圾桶,花里胡哨的
点赞 评论 收藏
分享
03-29 14:19
门头沟学院 Java
你背过凌晨4点的八股文么:加油同学,人生的容错率很高,只是一个暑期罢了,后面还有很多机会!
点赞 评论 收藏
分享
评论
20
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务