栈的压入、弹出序列

老规矩，先上自己的解法，思路是在出栈序列中的任何一个值，我们去找它入栈序列中的前面的已经入过栈的值，则这些已经入栈的数在当前处理的出栈序列后的值必须逆序。

import java.util.*;

public class Solution {
    public boolean IsPopOrder(int [] push,int [] pop) {
        if (push == null || push.length == 0)
            return true;
        if (push.length == 1)
            return push[0] == pop[0];

        Set<Integer> popped = new HashSet<>();
        for (int i = 0; i < pop.length; ++i) {
            Set<Integer> set = new HashSet<>();
            int tmp = pop[i];

            int index = indexOf(push, tmp);
            if (index == -1) 
                return false;

            for (int j = index-1; j >= 0; --j) {
                if (!popped.contains(push[j])) {
                    set.add(push[j]);
                }
            }

            for (int j=i+1, k=index-1; j<pop.length && k >=0; ) {
                if (!set.contains(push[k])) {
                    --k;
                    continue;
                }
                if (!set.contains(pop[j])) {
                    ++j;
                    continue;
                }
                if (pop[j] == push[k]) {
                    ++j;
                    --k;
                } else {
                    return false;
                }
            }
            popped.add(tmp);
        }
        return true;
    }

    // 判断target在数组arr中的位置
    private int indexOf(int[] arr, int target) {
        int index = -1;
        for (int i = 0; i < arr.length; ++i) {
            if (arr[i] == target) {
                index = i;
                break;
            }
        }
        return index;
    }
}

代码量偏大，虽然思路是对了，但是没有找到解决问题的精简方法。

import java.util.*;

// 遍历pop集合，看栈顶元素是否为目标值，是弹出，否则继续push继续判断
public class Solution {
    public boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack<Integer> stack = new Stack<>();
        int index = 0;
        for (int i : popA) {
            while (true) {
                if (!stack.isEmpty() && stack.lastElement().equals(i)) {
                    stack.pop();
                    break;
                } else {
                    if (index < pushA.length) {
                        stack.push(pushA[index]);
                        index++;
                    } else {
                        break;
                    }
                }
            }
        }
        return stack.isEmpty();
    }
}