代码随想录算法训练营打卡Day13 | LeetCode239 滑动窗口最大值、LeetCode 347前k个高频元素

摘要

如何用双端队列deque实现单调队列，单调队列是指，队列中的元素顺序按非递增、非递减、递增、递减中的一种的队列。
- 队首根据窗口的滑动出队
- 队尾根据元素的大小出队
优先级队列priority_queue，大顶堆、小顶堆的使用

今日学习的视频和文章

代码随想录滑动窗口最大值
代码随想录前k个高频元素
C++Primer 双端队列部分
数据结构C++语言版第二版（清华大学出版社）大顶堆、小顶堆的实现
C++函数指针

LeetCode239 滑动窗口最大值

239. 滑动窗口最大值 - 力扣（Leetcode）

初见题目的想法：
- 这道题目中，滑动窗口中可能的最大值有两种排除可能方式：
  1. 滑动窗口滑过了某个可能的最大值，即该可能最大值不再被包含在当前的滑动窗口内。如以下例子，3不在窗口内。
```
1 3 [1 2 0] 5
```
  1. 有一个新的可能最大值进入滑动窗口，其他比这个可能最大值小且有可能在同一个滑动窗口内的值都不可能成为滑动窗口的最大值。可见，在如下的滑动过程中，3和2之间的1，不会有成为滑动窗口最大值的可能。
```
1 [3 1 2] 0 5
1 3 [1 2 0] 5
```
而滑动窗口中的元素先进先出，这让人很自然的联想到队列，所以上述的两个排除可能最大值的方式对应到元素的出队方式就是：
1. 队首的元素根据窗口的滑动出队，如果队首的元素已经不在当前滑动窗口内，则出队
2. 队尾的元素根据滑动窗口包含的新的值出队，如果队尾的元素比滑动窗口包含进的新的一个值小，则队尾的元素出队
由于需要从队首和队尾两个方向将元素出队，所以考虑使用双端队列deque

完整的题解代码如下，此处的题解代码的单调队列保存的是元素的下标

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> q;
        for (int i = 0; i < nums.size(); i++) {
            if (!q.empty() &&  i - q.front() == k) {
                q.pop_front();
            }
            while (!q.empty() && nums[i] > nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
            if (i + 1 >= k) {
                res.push_back(nums[q.front()]);
            }
        }
        return res;
    }
};

看了讲解之后的思考：
- 维护单调队列的关键：尝试新入队的元素不断与队尾元素比较，若队尾元素和尝试新入队的元素不符合我们定义的顺序，则让队尾元素出队。而队首元素的出队是由于滑动窗口的滑动导致包含的元素的变化。

LeetCode 347前k个高频元素

347. 前 K 个高频元素 - 力扣（Leetcode）

解题思路：

先遍历一遍数组nums，使用哈希表unordered_map来记录各元素的出现的频率。
由于题目只要求返回前k个高频元素，所以可以考虑将频数在后n-k个的元素排除。
如果使用大顶堆，当堆中元素个数到达k个时，由于后面还有至少n-k个元素没有进入堆中排序，所以也无法确定堆顶是否是在前k个高频元素中。
如果使用小顶堆，当堆中元素到达k个时，再往堆中加入一个元素并调整为小顶堆后，由于堆顶是当前k+1个元素内频数最小的元素，所以可以确定堆顶元素中不会在前k个高频元素中。将堆顶元素弹出即可（因为已经确定有k个元素的频数大于堆顶元素的频数，自然最后的答案不会有目前的堆顶元素）。

使用大顶堆	使用小顶堆
对所有元素按频数进行堆排序，然后从堆顶取k个元素，即为题目要求的k个高频元素	在遍历元素时，保持堆中的元素为k个，遍历完成时，小顶堆中保留的元素即为题目要求的k个元素
实际上是对所有元素按频数进行排序，然后取前k个高频元素	实际上就是优先队列的思想，频数高的保留在队列中，频数低的优先出队

完整题解代码如下

class Solution {
public:

    class minHeapCmp {
    public:
        bool operator()(const pair<int, int>& l, const pair<int, int>& r) {
            return l.second > r.second;
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        for (auto& iter : nums) {
            map[iter]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, minHeapCmp> minHeap;
        for (auto& iter : map) {
            minHeap.push(iter);
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }

        vector<int> ans(k);
        for (int i = k - 1; i >= 0; i--) {
            ans[i] = minHeap.top().first;
            minHeap.pop();
        }
        return ans;
    }
};

疑惑及要注意的地方：
- 优先级队列自定义的比较规则，为什么是l.second > r.second，我没有深入的理解，等之后复习完树的内容后，我会尝试用C++实现一个可以自定义比较规则的堆来帮助理解。
- STL为编程提供了很多便利，但不仅要知道怎么用，更要在使用的过程中思考STL是如何实现的。排斥STL和过度依赖STL都是不利于学习的。