剑指offer栈的压入弹出序列Java

jiezi

5 年前

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

首先要理解为什么栈的压入顺序一定的情况下却可以有不同的弹出顺序，就是在栈的压入过程中可以向外弹元素，不一定是全部元素进栈才开始向外弹栈，所以会产生不同的弹栈顺序。
1. 题目给的是 ArrayList，使用这个作为辅助空间
然后就是借助一个辅助空间，将压栈的序列储存起来，储存过程中判断是否和弹栈序列一致，如果一致就让弹栈序列指向后一位，等压栈序列全部进辅助空间后，在开始反向遍历一次，因为题目说明没有重复元素，所以进辅助空间过程中判断过的元素可以重复判断，不会出错，遍历过程中判断是否和弹栈序列元素相等，相等就弹栈序列指向后一位，并且辅助空间也指向下一个元素，不相等就只让辅助空间指向下一个元素，这样反向遍历完辅助空间后如果弹栈序列没有走到最后，就说明不是正确的弹栈序列，如果走到了最后就是正确序列。

import java.util.ArrayList;

public class Solution {public boolean IsPopOrder(int [] pushA,int [] popA) {if(pushA.length == 0 || popA.length == 0)
            return false;
        int i = 0;    // 指向压栈序列的指针
        int j = 0;    // 指向弹栈序列的指针
        ArrayList<Integer> helpList = new ArrayList<>();    // 储存压栈序列的辅助空间
        while(i < pushA.length){    // 第一次遍历把压栈序列放入辅助空间中
            helpList.add(pushA[i]);    
            if(helpList.get(i) ==  popA[j]){    // 如果有相等的就让弹栈序列指针 ++。j++;
            }
            i++;
        }
        i = i-1;    // 这里是细节，最后 i =pushA.length 所以要 -1.
        while(i>= 0 && j < popA.length){    //i>= 0 也是细节，如果只是大于 0，0 位置的元素就没办法判断了。if(helpList.get(i)== popA[j]){    
                i--;
                j++;
            }else{i--;}
        }
        return j == popA.length ? true:false;    // 根据弹栈序列的指针是否走到最后判断是不是弹栈序列。}
}

2：使用 Stack

使用栈结构的好处就是可以省去上面方法过程中的重复判断，因为可以判断到一个相等就直接弹出。

import java.util.Stack;

public class Solution {public boolean IsPopOrder(int [] pushA,int [] popA) {if(pushA.length == 0 || popA.length == 0)
            return false;
        Stack<Integer> temp = new Stack<>();
        int popIndex = 0;
        for(int i = 0 ; i < pushA.length; i++){temp.push(pushA[i]);
            while(!temp.isEmpty() && temp.peek() == popA[popIndex]){temp.pop();
                popIndex++;
            }
        }
        return temp.isEmpty();}
}

方法 2 参考：Alias

剑指offer栈的压入弹出序列Java

1. 题目描述

2. 思路