一种判断合法进出栈序列的方法

问题描述

    假设我们有一组数字按从小到大的顺序执行进栈和出栈的操作，比如我们有数字0, 1, 2, 3, 4, 5, 6, 7, 8, 9。它们按照顺序混合执行push, pop操作。其中pop操作返回的数字组成一个序列。那么，当我们给定一个序列的时候，能否判断这个序列是可以通过这么一组push, pop操作形成呢？

 

问题分析

    对于这个问题，一开始确实有点不太好分析。虽然数字都是按照顺序入栈的，但是它们出栈的顺序却不确定。假设我们以一组数字0， 1， 2为例来看它们push, pop操作形成的序列。那么它们对应如下的一些情况：

 

1. push 0, pop 0, push 1, pop 1, push 2, pop 2  (0, 1, 2)

2. push 0, pop 0, push 1, push 2, pop 2, pop 1 (0, 2, 1)

3. push 0, push 1, pop 1, pop 0, push 2, pop 2 (1, 0, 2)

4. push 0, push 1, pop 1, push 2, pop 2, pop 0 (1, 2, 0)

5. push 0, push 1, push 2, pop 2, pop 1, pop 0 (2, 1, 0)

     按照这里的分析，至少上面这些序列都是通过入栈出栈操作形成的合法序列。而对于上面这三个数字来说，它们所能够形成了所有排列有6个。针对上面的5个序列来看，有一个排列是不能生成的。这个序列是2, 0, 1。

    那么对于这个不能生成的序列，它有什么特点呢？因为在这里，当2出栈的时候，在栈里它下面的元素必然都是比它小的元素。一旦这些比它小的元素压入栈之后并没有马上出栈，它们就只能等到上面这些大的元素出了之后才能出了。

    而且这个规律还要一个比较有意思的递归特性。对于任何一个元素来说，当它进栈的时候，它下面的元素必然都比它小。因为我们前面所有元素都是按照从小到大的顺序进栈的。而出栈的时候呢，当这个大的元素出栈的时候，后面接着要出栈的元素里只要是原来它下面的元素，就必然一个比一个小。所以，我们也可以概括成这样，对于栈里任何一个出栈的元素来说，生成的序列里它后面所有比它小的元素必然构成一个递减的序列。 所以，按照这个规律，我们可以来判断一个给定的序列是否为通过入栈出栈生成的。

 

public static boolean validSequence(int[] a) {
    for(int i = 0; i < a.length; i++) {
        int cur = a[i];
        for(int j = i + 1; j < a.length; j++) {
            if(a[j] < a[i]) {
                if(a[j] > cur) return false;
                else cur = a[j];
            }
        }
    }
    return true;
}

    这里的代码实现就是从一个序列里遍历每个元素，去看后面所有比它小的元素是否构成一个递减的序列，如果没有就返回false，否则返回true。这种实现比较简单，但是性能方面有一些值得改进的地方。它的时间复杂度为O(N^2)。因为对于某个元素来说，比如3，如果我们判断过后面所有比它小的元素0, 1, 2都是符合条件的。对于序列中3后面的元素，比如4来说，对于0, 1, 2的情况其实都不用再去判断了。同样，对于比3小的元素，我们这么遍历的时候都可以直接跳过去。

    所以，为了实现这么一个改进，我们新增加了一个数组boolean[] marked，用来表示前面已经比较过的元素，一旦这些比较过的元素已经符合前面描述的递减关系，我们就标记marked[i] = true，在循环中把这些情况的跳过去。

 

pulic static boolean isValid(int[] a) {
    boolean[] marked = new boolean[a.length];
    for(int i = 0; i < a.length; i++) {
        if(marked[i]) continue;
        int cur = a[i];
        marked[i] = true;
        for(int j = i + 1; j < a.length; j++) {
            if(marked[j]) continue;
            if(a[j] < a[i]) {
                if(a[j] > cur) return false;
                else cur = a[j];
                marked[j] = true;
            }
        }
    }
    return true;
}

     按照这种思路，上面代码的时间复杂度在最理想情况下可以达到O(N)。

 

总结

    这是一个看似不起眼的问题，实际上深入分析的时候并不好解决。需要发现它的一些规律。从它引申出来的一些问题比如这种序列的个数之类的包含了不少数学的东西，比如卡塔兰数之类的。比较有意思，以后有机会再深入的分析分析。 

 

参考材料

 Algorithms