Daily LeetCode – day0033 0946. Validate Stack Sequences

// 0946. Validate Stack Sequences
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        int len = pushed.length;
        boolean[] pop = new boolean[len];
        int i = 0;
        int j = 0;
        while (j < len) {
            if (pushed[i] == popped[j]) {
                pop[i] = true;
                ++j;
                if (j == len) return true;
                while (pop[i]) {
                    --i;
                    if (i < 0) {
                        ++i;
                        while (pop[i]) {
                            ++i;
                        }
                    }
                }
            } else {
                ++i;
                if (i == len) return false;
                while (pop[i]) {
                    ++i;
                    if (i == len) return false;
                }
            }
        }
        return true;
    }
}
学习笔记:
这是一道栈的模拟算法问题,我一开始用了栈,花了11ms。
后来在原本数组上面操作,但是发现还是有问题,数据会丢失维度,后来多建一个数组记录pushed数组中的元素是否有使用过,本来我觉得这样写得更复杂了,空间会省,但可能更慢,结果就1ms跑完了。
今天也是8月最后1天,完成了8月每日1题全部打卡挑战,完美。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。