剑指offer面试题系列

题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出序列。假设压入栈的所有数字均不相等。例如：序列1、2、3、4、5是某栈的压入序列，序列4、5、3、2、1是该压栈序列对应的弹出序列，但4、3、5、1、2就不是该压栈序列对应的弹出序列。

分析

后压入栈的元素不可能比先压入栈的元素先出栈，利用栈的这条定理就可以想明白这个问题，最开始的思路是从两个数组中找出某种规律来，就像前面做过的一道题，利用二叉树的先序遍历和中序遍历来重建二叉树。但是最终由于处理起来太过复杂而没有实现。

这个思路行不通，只能用一个辅助栈来实现了。

就拿例子中的序列来说 1、2、3、4、5，因为栈弹出的元素永远在栈顶，所以要想弹出4，必须将1、2、3依次入栈。于是1、2、3 弹出的顺序只能是 3、2、1，在下面的版本一种就是利用这种想法实现的，但是没有估计到在弹出一次栈顶元素后复杂的情况。

版本二的思路就是：遍历出栈数组，因为出栈序列的元素必须是栈顶元素，所以必须将所遍历到元素前面的元素压入栈中，继续往前遍历，如果遍历到的元素已经入栈（这个通过cur游标和出栈数组在入栈数组中的位置pos的关系来判断），则直接出栈，与出栈元素比较，相等则继续遍历，不等则break跳出；如果遍历到的元素没有入栈，则将入栈序列中该元素前面的元素全部入栈。以此类推。

代码实现

版本一（错误版本）：

public static boolean IsRight(int[] pushArr, int[] popArr) {
        boolean isRes = true;
        int pos = FindPos(popArr[0], pushArr);
        if (pos == -1)
            return false;

        int rlength = pushArr.length - 1 - pos;
        int llength = pos;
        int k = 0;
        if (rlength > 0) {
            for (k = 1; k <= rlength; k++) { // 比较右半部分
                if (pushArr[k + pos] != popArr[k]) {
                    isRes = false;
                    break;
                }
            }
        }

        if (llength > 0) {
            for (; k <= popArr.length - 1 && pos >= 0; k++) { // 比较左半部分
                if (popArr[k] != pushArr[--pos]) {
                    isRes = false;
                    break;
                }
            }
        }

        return isRes;
    }

    // find the position in arr
    public static int FindPos(int num, int[] arr) {
        int i = 0;
        int pos = -1;
        while (i < arr.length) {
            if (arr[i] == num) {
                pos = i;
                break;
            }
            i++;
        }

        if (pos >= 0)
            return pos;
        else
            return -1;
    }

版本二：

package com.study;
class MainStack {
    private static final int MAXSIZE = 10;
    private static int point = 0; // 指向栈顶
    private static int[] arr = new int[MAXSIZE];

    public static int getTop() {
        if (point > 0)
            return arr[point - 1];
        else
            return -1;
    }

    public static boolean isEmpty() {
        return point <= 0;
    }

    public static void push(int data) {
        if (point < MAXSIZE) {
            arr[point] = data;
            point++;
        } else {
            System.out.println("The stack is full");
        }
    }

    public static int pop() {
        if (point > 0) {
            point--;
            return arr[point];
        } else {
            return -1;
        }
    }
}

public class suanfa14 {
    private static int[] push = { 1, 2, 3, 4, 5, 6, 7 };
    private static int[] pop = { 5, 4, 6, 7, 3, 2, 1 };
    private static int[] pop1 = { 4, 5, 3, 1, 2 };

    /*
     * 新版，利用两个栈来完成判断
     */
    public static boolean Judge(int[] pushArr, int[] popArr) {
        boolean DoMatch = true;
        int cur = 0; // pushArr中已经压入栈元素界限
        int pos = 0; //popArr中的元素在pushArr中的位置
        for (int i = 0; i < popArr.length; i++) {
            pos = FindPos(popArr[i], pushArr);
            if (MainStack.getTop() != popArr[i]) { // 如果出栈序列的元素不在栈顶上
                if (pos >= cur) { // 如果元素还没有被压入栈
                    while (cur <= pos) { // 将其前面的元素直接压栈
                        MainStack.push(pushArr[cur]);
                        cur++;
                    }
                }
            }

            // 比较过程
            if (MainStack.pop() != popArr[i]) {
                DoMatch = false;
                break;
            }

        }

        return DoMatch;
    }

    public static int FindPos(int num, int[] arr) {
        int i = 0;
        int pos = -1;
        while (i < arr.length) {
            if (arr[i] == num) {
                pos = i;
                break;
            }
            i++;
        }

        if (pos >= 0)
            return pos;
        else
            return -1;
    }

    public static void main(String[] args) {
        System.out.println(Judge(push, pop));
    }
}

备注

需要注意在判断出栈数组中的元素是否入栈时，pos和cur的比较关系需要加相等符号，因为可能只有只需要将一个元素入栈即可。

总结

理性分析能力还是需要多加锻炼，当你茫无头绪时，一定要记得去努力寻找规律，条分缕析。越来越发现自己一个思维上的不好的习惯就是：过分依赖长期训练所产生的一种感觉，如果拿到这个题，没有找到感觉，就会不知所措。这样的思维高三消失了一年，现在毛病又来了，一定要改，要理性的思考问题，这样才能不知会做熟题，也会做生题。