栈的压入、弹出序列

题目描述

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

示例 1：

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2：

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

提示：

1. 0 <= pushed.length == popped.length <= 1000
2. 0 <= pushed[i], popped[i] < 1000
3. pushed 是 popped 的排列。

题目链接

Leetcode

题目解答

解法一

栈模拟，使用辅助栈模拟出栈和入栈的过程，先按压入顺序把元素入栈，然后比较栈顶元素与弹出序列下标指向元素是否相同，如果是，则栈顶元素出栈，同时弹出序列下标后移，重复这个过程，直到压栈序列中的每个元素都已经入过栈。此时，就可以通过判断辅助栈是否为空，来确定输入的弹出序列是否为压入序列的正确弹出序列。

时间复杂度:$O(n)$ 空间复杂度:$O(n)$

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int i =0;
        Stack<Integer> stack = new Stack<>();
        for (int num : pushed) {
            stack.push(num);
            while (!stack.isEmpty() && popped[i] == stack.peek()) {
                stack.pop();
                i++;
            }
        } 
        return stack.isEmpty();
    }
}

执行用时：2 ms, 在所有 Java 提交中击败了96.35%的用户
内存消耗：38.2 MB, 在所有 Java 提交中击败了38.89%的用户

解法二

数组模拟，本质上还是栈模拟的思路，区别是基于数组手动维护入栈和出栈操作，这种方式相对于编程语言提供的原生 Stack，能减少出入栈过程中不必要的操作，从而提升程序运行的效率。

时间复杂度:$O(n)$ 空间复杂度:$O(n)$

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int top = 0, pop = 0;
        int[] stack = new int[pushed.length];
        for (int num : pushed) {
            stack[top++] = num;
            while (top > 0 && stack[top - 1] == popped[pop]) {
                top--;
                pop++;
            }
        }
        return top == 0;
    }
}

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38 MB, 在所有 Java 提交中击败了78.36%的用户