Day13单调队列和优先级队列
By HQWQF 2023/12/25
笔记
239.滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶：
你能在线性时间复杂度内解决此题吗？
示例 1：输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7
解法：单调队列
最简单的方法就是暴力解法，对于不同位置的窗口遍历其中的3个元素得到最大值。
然而为了得到当前窗口中的最大值而反复遍历实际上做了多余的工作，比如在滑动窗口到一个新的位置后，虽然我们已经在上一个窗口得知了一些元素的大小关系，然而我们还是在这个窗口内重新寻找他们的大小关系。
其实我们只要考虑那些有可能成为窗口内最大值的元素。
首先，滑动窗口一端去除元素，一段加入元素的行为很像队列，我们使用队列来处理待考虑的元素。
关于如何只考虑那些有可能成为窗口内最大值的元素。 有几点：
- 如果待加入的元素比已经考虑队列中的某些元素更大，我们可以将这些元素全部排除出队列，因为待加入的元素在滑动窗口中的剩余存在时间比他们更长，值也比他们大，因此这些元素都不需要考虑。
- 为了方便首先将比待加入元素小的元素全部排除出队列的操作，我们可以尝试从开始就维护一个单调递减的队列，这样我们就可以从队列尾开始尝试排除元素而不需要遍历所有元素。
- 而且对于这样一个单调递减的考虑队列，其队列首的元素就是我们的目标元素。
这样的队列我们称之为单调队列
由于我们需要将元素从尾部弹出，我们需要使用双端队列deque来实现单调队列这种数据结构。
单调队列
class MyQueue { //单调队列（从大到小）
public:deque<int> que; // 使用deque来实现单调队列// 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。// 同时pop之前判断队列当前是否为空。void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。// 这样就保持了队列里的数值是单调从大到小的了。void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。int front() {return que.front();}
};
这样我们只需要配合滑动窗口pop和push元素，滑动窗口移动时将单调队列的首元素作为最大值记录即可。
代码
class Solution {
private:class MyQueue { //单调队列（从大到小）public:deque<int> que; // 使用deque来实现单调队列// 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。// 同时pop之前判断队列当前是否为空。void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。// 这样就保持了队列里的数值是单调从大到小的了。void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。int front() {return que.front();}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue que;vector<int> result;for (int i = 0; i < k; i++) { // 先将前k的元素放进队列que.push(nums[i]);}result.push_back(que.front()); // result 记录前k的元素的最大值for (int i = k; i < nums.size(); i++) {que.pop(nums[i - k]); // 滑动窗口移除最前面元素que.push(nums[i]); // 滑动窗口前加入最后面的元素result.push_back(que.front()); // 记录对应的最大值}return result;}
};
347.前 K 个高频元素
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
- 输入: nums = [1,1,1,2,2,3], k = 2
- 输出: [1,2]
示例 2:
- 输入: nums = [1], k = 1
- 输出: [1]
提示：
- 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 $O(n \log n)$ , n 是数组的大小。
- 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
- 你可以按任意顺序返回答案。
解法：哈希表，优先级队列
首先我们需要用一个哈希表来存储元素及其频率，所以我们要用map。
为了获取频率前 k 高的元素，我们可以维护一个size不大于k的优先级队列，将键值对加入优先级队列，最后形成的优先级队列的倒序就是我们需要的结果。
那么什么是优先级队列呢？
优先级队列中的每个元素都有一个与之关联的优先级。具有较高优先级的元素在队列中排在较低优先级的元素之前，队列头的元素就是优先级最高的。
每次push进去元素都会触发优先级队列的排序机制，将元素放到合适的位置，以维持其有序性，每次pop出来的就是优先级最高元素的。
为了维护一个size不大于k的优先级队列，我们可以在每次push进元素时检测size是否大于k，大于则pop元素。根据题目和优先级队列的性质，频率低的元素应该优先级更高。
关于优先级队列的定义我们需要了解：
//默认
std::priority_queue<int> maxHeap;
//默认情况只需要给数据类型，数据大的优先级大//非默认priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;//除了数据类型外，第二个参数是用什么作为存储元素的底层容器，第三个参数是比较器//比如mycomparison是一个类//类中有一个名为operator的bool类型的方法，在判断一个元素是否比另一个元素的优先级高时调用。//其返回值就是结果class mycomparison {public:bool operator()(const pair<int, int>& hs1, const pair<int, int>& hs2) {return hs1.second > hs2.second;//降序}};
//如何operator方法返回值为true，说明第二个参数比第一个参数优先级高代码
class Solution {
public:// 小顶堆class mycomparison {public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {// 要统计元素出现频率unordered_map<int, int> map; // map<nums[i],对应出现的次数>for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;}// 对频率排序// 定义一个小顶堆，大小为kpriority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;// 用固定大小为k的小顶堆，扫面所有频率的数值for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为kpri_que.pop();}}// 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组vector<int> result(k);for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}
};
