代码随想录算法训练营第11天｜栈与队列Part02

记录题目：

• 滑动窗口最大值
• 前 K 个高频元素

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。你只能看到滑动窗口内的 k 个数字，窗口每次只向右移动一位。

请返回滑动窗口中的最大值序列。

LeetCode239. 滑动窗口最大值

单调队列类 MonoQueue 实现：

class MonoQueue {
    constructor() {
        this.queue = [];  // 储存元素的队列，维护一个单调递减序列（队头最大）
    }

    // 将新元素加入队尾，并维护队列的单调性
    push(value) {
        // 若新元素大于当前队尾元素，则不断弹出队尾，保持队列递减
        while (this.queue.length && value > this.queue[this.queue.length - 1]) {
            this.queue.pop();
        }
        this.queue.push(value);
    }

    // 如果当前离开窗口的元素恰好是队头最大值，则将其移除
    pop(value) {
        if (this.queue.length && this.queue[0] === value) {
            this.queue.shift();
        }
    }

    // 获取当前窗口内的最大值
    getMax() {
        return this.queue[0];
    }
}

给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率最高的 k 个元素。返回结果可以按 任意顺序。

LeetCode347. 前 K 个高频元素

这道题目主要涉及到如下三部分：

1. 要统计元素出现频率
2. 对频率排序
3. 找出前K个高频元素

统计频率最合适的方式是使用哈希表，其构造过程时间复杂度为 O(n)。在此基础上，如果使用快速排序对所有元素按频率排序，时间复杂度为 O(nlogn)，但这会引入额外“副作用”：即我们仅需要前 k 个高频元素，却对所有元素都进行了排序，这实际上是对问题规模的不必要扩张。

从一个可类比的角度出发，我称之为：

复杂度守恒定律

问题规模 ≈ 时间复杂度贡献 + 空间复杂度贡献

且两者应与实际需求成比例。

在这个问题中，如果我们避免对前 k 个之外的元素频率排序，时间复杂度理应降低。由于空间开销主要集中在哈希表上，若空间未变，那么时间复杂度降低的空间确实存在。

这启发我们：应该存在一种算法，能在不排序所有元素的前提下，仅维护出前 k 个频率最高的元素。堆（优先队列）正好满足这个需求：

1. 使用最小堆维护一个大小为 k 的窗口；

2. 对所有元素频率依次入堆，维护堆中始终为当前频率最高的 k 个元素；

3. 最终堆中的元素即为所求。

该方法时间复杂度为 O(nlogk)，其中 n 为不同元素的个数，k 为所需高频元素数量。当 k = n 时，退化为堆排序，其复杂度为 O(n \log n)，与快速排序一致。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
    const map = new Map();
    const res = [];
    //使用 map 统计元素出现频率
    for (const num of nums) {
        map.set(num, (map.get(num) || 0) + 1);
    }
    //创建小顶堆
    const heap = new PriorityQueue((a, b) => a.value - b.value)
    for (const [key, value] of map) {
        heap.enqueue({ key, value });
        if (heap.size() > k) heap.dequeue();
    }
    //处理输出
    while (heap.size()) res.push(heap.dequeue().key);
    return res;
};