LeetCode 946. Validate Stack Seq

@(LeetCode)

问题描述

给定两个数组 pushed 和 popped，数组内部元素均不相同。如果在一个空栈上操作，能得出 pushed 和 popped 的结果，则返回 true。

栗 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

解释：
push(1), push(2), push(3), push(4), pop() -> 4, pop() -> 3,
push(5), pop() -> 5。
此时栈顶为 2，而需要 pop 的值为 1，因此无法出栈。

注意：

1. 0 <= pushed.length == popped.length <= 1000
2. 0 <= pushed[i], popped[i] < 1000
3. pushed 是 popped 的排列数。
4. pushed 和 poped 内部元素值不同。

想看英文原文的戳这里。

解题思路

我的解法

初始为空栈，在经过一系列的进栈和出栈操作后，如果最终栈为空，则说明操作可行。

思路比较简单，只需要逐个对比当前 push 和 pop 的元素：

• 若需要入栈和出栈的元素相等，那么出入栈是匹配的，元素不用入栈，省去入栈和出栈的过程。此时 pop 的元素会指向下一个，需要循环判断当前栈顶元素是否与其匹配，从而进行出栈操作。
• 若不相等，则进栈。

如果最终栈为空，则返回 true。

js 代码如下：

/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
var validateStackSequences = function(pushed, popped) {
    let list = new Array()
    let i = 0
    let j = 0

    while (i < pushed.length) {
        // 相等，不需要 push
        if (pushed[i] === popped[j]) {
            // pop 元素指向下一个
            j += 1

            // 循环判断 list 栈顶是否可以出栈
            while (list.length > 0 && (list[list.length - 1] === popped[j])) {
                list.pop()
                j += 1
            }
        } else {
            // 入栈
            list.push(pushed[i])
        }

        i += 1
    }

    if (list.length === 0) {
        return true
    }

    return false
};

其他解法

其他的解法思路差不多，只不过其没有判断当前入栈的元素和出栈的元素是否相同，统一直接入栈，然后再不断对比栈顶元素。

以上解法中空间复杂度为 O(N)。在讨论区发现有一种 O(1) 的解法，使用原 pushed 的空间达到同样的效果，比较巧妙。

可能有同学会担心 pushed 元素被覆盖的问题。 在这种方式中，如果栈顶元素匹配，索引会回退，始终占据之前的空间，因此不会覆盖。

😆自己在纸上走一遍过程就清楚了。

Java 代码如下：

public boolean validateStackSequences(int[] pushed, int[] popped) {
    int i = 0, j = 0;
    for (int x : pushed) {
        // 直接进栈，使用原来的空间
        pushed[i++] = x;
    
        // 不断对比栈顶元素
        while (i > 0 && pushed[i - 1] == popped[j]) {
            --i; 
            ++j;
        }
    }

    return i == 0;
}