给定数组arr1是入栈顺序，arr2是出栈顺序，判断出栈顺序是否合理java

思路：借助一个辅助栈，我们按入栈的顺序依次将数组 arr1 中的元素压入栈中，同时每次都判断当前栈顶元素是否与数组 arr2 中的第一个元素相等。如果相等，则将该栈顶元素弹出，并将数组 arr2 中的第一个元素移到下一个位置，继续比较栈顶元素是否与数组 arr2 中的第一个元素相等。最终，如果辅助栈为空，则表示出栈顺序合法，否则不合法。

代码如下：

public static boolean isPopOrder(int[] pushSequence, int[] popSequence) {
    if (pushSequence == null || popSequence == null)
        return false;
    Stack<Integer> stack = new Stack<>();
    int index = 0; // popSequence 的索引
    for (int i = 0; i < pushSequence.length; i++) {
        stack.push(pushSequence[i]);
        while (!stack.isEmpty() && stack.peek() == popSequence[index]) {
            stack.pop();
            index++;
        }
    }
    return stack.isEmpty();
}

时间复杂度：O(n)，其中 n 是数组的长度。需要遍历两个数组，每个元素最多进出栈一次。

空间复杂度：O(n)，需要借助一个辅助栈。