946. 验证栈序列

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

示例 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 <= pushed.length <= 1000
• 0 <= pushed[i] <= 1000
• pushed 的所有元素 互不相同
• popped.length == pushed.length
• popped 是 pushed 的一个排列

辅助栈，贪心

使用一个双端队列来模拟栈操作，遍历 pushed 序列将元素依次压入栈，并在每次压入后检查栈顶元素（即队列末尾元素）是否与 popped 序列当前元素匹配。如果匹配则弹出栈顶元素并移动 popped 序列指针。最终通过检查栈是否为空来判断 pushed 和 popped 序列是否可以通过合法的栈操作得到对方。

假设我们有以下两个序列：

• pushed = [1, 2, 3, 4, 5]
• popped = [4, 5, 3, 2, 1]

我们要验证按照pushed序列压栈后，是否可以通过某种操作顺序得到popped序列。

1. 初始化：创建一个双端队列d作为栈的模拟，以及两个指针i和j分别用于遍历pushed和popped数组。
2. 模拟压栈操作：遍历pushed数组，依次将元素压入栈（双端队列的尾部）。
3. 检查并弹栈：每次压栈后，循环检查栈顶元素是否与popped[j]相等。如果相等，则弹栈（移除双端队列的尾部元素），并将j加1（向前移动popped的指针）。
   • 对于我们的例子，当pushed的4被压栈后，栈顶元素4等于popped[j]（j=0时，popped[j]=4），因此4被弹栈，j变为1。
   • 接下来，5被压栈并立即弹栈，因为它也匹配popped[j]（现在j=1，popped[j]=5）。
4. 重复以上过程，直到pushed数组中的所有元素都被处理。
5. 验证栈是否为空：最后，如果模拟的栈（双端队列）为空，说明可以通过给定的弹栈序列popped来复原栈，返回true。如果栈非空，说明无法通过该弹栈序列复原，返回false。

在我们的例子中，由于所有pushed中的元素都能按popped的顺序弹出，最终栈为空，因此返回true。

根据题意，利用元素各不相同，我们使用一个栈来处理 pushed 数组，每次将 pushed[i] 放入栈中，然后比较当前栈顶元素是否与待弹出元素相同（使用变量 j 来代指当前待弹出元素下标），若相等则弹栈并进行 j 自增，当所有的元素处理完后，栈为空说明栈序列合法。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> d = new ArrayDeque<>();
        
        // i用于遍历pushed序列，j用于遍历popped序列。注意push、pop和peek对应的是first
        for (int i = 0, j = 0; i < pushed.length; i++) {
            d.addLast(pushed[i]);
            // j的增加只有在前面的条件!d.isEmpty() && d.peekLast() == popped[j]为真时才会发生。
            // 这意味着，如果栈顶元素与popped[j]不匹配，j就不会增加，从而避免了访问popped数组时的索引越界错误。
            // 注意题目说pushed和poped中的每个值都不重复。
            // push完就要检查是否需要pop
            // i每次都自增，j有条件自增。
            // 贪心。入完栈就检查能否出栈。
            while (!d.isEmpty() && d.peekLast() == popped[j]) {
                j++;                
                d.pollLast();
            }
        }
        
        // 如果模拟的栈为空，说明pushed序列可以通过一定的出栈顺序得到popped序列
        // 否则，返回false
        return d.isEmpty();
    }
}

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

双指针-原地修改pushed数组，使用变量 idx 代指栈顶下标。入队后要增加idx，出队后要减少idx，最后检查idx是否为0

我们也可以直接利用 pushed 充当栈，使用变量 idx 代指栈顶下标，变量 j 指向 popped 中待弹出的元素。

该做法好处无须额外空间，坏处是会修改入参数组。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        // idx指当前要修改的位置
        int n = pushed.length, idx = 0;
        
        for (int i = 0, j = 0; i < n; i++) {
            pushed[idx] = pushed[i];
            idx++;
            
            while (idx > 0 && pushed[idx - 1] == popped[j]) {
                j++;
                idx--;
            }
        }
        
        return idx == 0;
    }
}

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