判断栈的出栈顺序合法性

栈的出栈顺序合法性是指给定一系列元素,如1 - N,按照从小到大的方式入栈,每个元素的出栈时机不定。题目给定一个出栈顺序,我们来判断这个出栈顺序有没有可能发生。

比如对[1,2,3,4,5,6,7,8,9]:

  • [1,2,3,4,5,6,7,8,9]是一个合法出栈序列
  • [9,8,7,6,5,4,3,2,1]也是一个合法序列
  • [4,5,3,2,7,6,1,8,9]也是一个合法序列
  • [3,4,5,1,2,9,8,7,6]就是一个非法序列

判断方法有两种,一种是对每一个值,其后所有小于它的值的数是一个降序排列。

另一种是模拟入栈和出栈,对出栈序列中每一个数值,如果它当前已经在栈顶,则出栈;如果不在,那么从入栈序列中取出下一个放入栈中;如果需要入栈时入栈序列已空,则这就是一个非法序列。


代码如下:

    public static boolean stackOrder(int[] nums){
        int[] origin=new int[]{1,2,3,4,5,6,7,8,9};
        //假定出栈序列也是1-9的数列
        Deque<Integer> q=new ArrayDeque<>();
        int index=0,i=0;
        for (i=0;i<nums.length;){
            if(!q.isEmpty()&& nums[i]==q.getLast()){
                q.pollLast();
                i++;
            }
            else {
                if(index<9) {
                    q.addLast(origin[index++]);
                }
                else break;
            }
        }
        return i==nums.length?true:false;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

扫码关注云+社区

领取腾讯云代金券