栈的压入、弹出序列

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

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

方法一：栈

我们可以模拟做类似题时的思路：如果栈顶数字不等于当前出栈数字，将入栈序列中的数字依次加入栈中，直到栈顶元素与当前出栈数字相等。

以示例 1 为例，idx1 指向压入序列，idx2 指向弹出序列。

1. 栈为空，先将 1 压入栈中
2. 栈顶数字 1 与数字 4 不相等，继续将 2 压入栈中
3. 栈顶数字 2 与数字 4 不相等，继续将 3 压入栈中
4. 栈顶数字 3 与数字 4 不相等，继续将 4 压入栈中
5. 栈顶数字 4 与数字 4 相等，
6. 栈顶数字 3 与数字 4 不相等，继续将 4 压入栈中
7. 栈顶数字 5 与数字 5 相等，将 idx1 和 idx2 后移
8. 数字 3 与栈顶数字 3 相等，idx2 后移，弹出栈顶元素
9. 数字 2 与栈顶数字 2 相等，idx2 后移，弹出栈顶元素
10. 数字 1 与栈顶数字 1 相等，idx2 后移，弹出栈顶元素
11. 此时栈为空，代表第二个序列是第一个序列的弹出序列，返回 true。

如果出现栈顶元素与当前弹出数字不相同且 idx1 已经指向入栈序列末尾，返回 false。

下图可以辅助理解

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        if(pushed.length != popped.length){
            return false;
        }
        int n = popped.length;
        Deque<Integer> stack = new LinkedList<>();
        int idx1 = 0, idx2 = 0;
        while(idx2 < n){
            //栈为空或者栈顶元素不等于当前弹出数字，直接将当前数字加入栈中
            while(idx1 < n && (stack.isEmpty() || stack.peek() != popped[idx2])){
                stack.push(pushed[idx1]);
                ++idx1;
            }
            //栈顶元素等于当前弹出数字
            if(stack.peek() == popped[idx2]){
                ++idx2;
                stack.pop();
            }else{//栈顶元素不等于当前弹出数字，出栈序列与入栈序列不匹配
                return false;
            }
        }
        return true;
    }
}

• 时间复杂度O(n)
• 空间复杂度O(n)