剑指 Offer 31: 栈的压入、弹出序列

[songyy5517]

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {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 之前弹出。

分析 这道题主要考察栈。因此，我们可以定义一个栈模拟元素压入弹出的过程。解题的关键在于弄清楚弹出元素的时机，即当栈顶元素和弹出序列当前元素相等，即可弹出元素，否则继续添加元素。

[songyy5517]

思路：利用辅助栈进行判断

1. 异常处理；
2. 定义辅助栈、弹出序列数组指针等相关变量
3. 将压入序列中的元素依次添加到辅助栈中，每次添加时判断栈顶元素是否与弹出序列当前元素相等： （1）若相等，则将栈顶元素弹出，并更新弹出序列数组指针，继续上述判断； （2）若不相等，则直接跳过，添加压入序列的下一个元素。
4. 若最终辅助栈为空，则返回true；否则，返回false。

复杂度分析：

• 时间复杂度： $O(N)$ ，遍历两个序列，需要 $O(N)$ 的时间， $N$ 为序列长度，每个元素最多入栈一次出栈一次，最多共有 $2N$ 次操作；
• 空间复杂度： $O(N)$ ，需要额外定义辅助栈，最多同时容纳 $N$ 个元素。

[songyy5517]

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        // 思路：利用辅助栈，判断序列是否匹配
        // 1. 异常处理
        if (pushed == null || popped == null)
            return false;

        // 2. 定义辅助栈 & 相关变量
        Stack<Integer> stack1 = new Stack();
        int p = 0;

        // 3. 循环将pushed序列中的元素依次添加至辅助栈中
        for (int i : pushed){
            stack1.add(i);

            // 若栈顶元素与popped当前位置元素相等，则弹出，直到不相等或栈为空。
            while (!stack1.isEmpty() && stack1.peek() == popped[p]){
                stack1.pop();
                p ++;
            }
        }

        // 4. 若辅助栈最终为空，则匹配成功；否则，匹配失败。
        return stack1.isEmpty();
    }
}

[songyy5517]

2023/1/19：遇到数组/Stack，一定要考虑越界的问题 2023/3/8 2023/10/10 2023/11/7 2023/12/13