📃 题目描述

题目链接：

• 剑指 Offer 31. 栈的压入、弹出序列 (opens new window)
• 946. 验证栈序列 (opens new window)

🔔 解题思路

直接模拟：

遍历数组 pushed，将pushed 的每个元素依次入栈；

• 每次将pushed 的元素入栈之后，如果栈不为空且栈顶元素与 popped 的当前元素相同，则将栈顶元素出栈，同时遍历数组 popped，直到栈为空或栈顶元素与 popped 的当前元素不同。
• 遍历数组 pushed 结束之后，每个元素都按照数组 pushed 的顺序入栈一次。如果栈为空，则每个元素都按照数组 popped 的顺序出栈，返回 true。如果栈不为空，则元素不能按照数组 popped 的顺序出栈，返回 false。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        // popped 数组下标
        int i = 0;
        // pushed 元素依次入栈
        for (int num : pushed) {
            stack.push(num);
            // 循环出栈
            while (!stack.isEmpty() && stack.peek() == popped[i]) {
                stack.pop();
                i ++;
            }
        }

        return stack.isEmpty();
    }
}

💥 复杂度分析

• 空间复杂度：O(N)
• 时间复杂度：O(N)