代码随想录算法训练营第十三天| 239. 滑动窗口最大值，347.前 K 个高频元素

本文主要是介绍代码随想录算法训练营第十三天| 239. 滑动窗口最大值，347.前 K 个高频元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

day12是休息，那天跑去刷蓝桥杯去了。。。
在这里插入图片描述
这道题和大数据寻找前K大的数据那道题还是有所不同的，优先级队列没办法处理这种两端出数据的窗口问题，这时候就得用单调队列来做

在这里插入图片描述
（图源代码随想录）
简单的说，单调队列就是使用deque双向队列维护三个函数：
push,pop,getMaxValue

由于我们需要保持当前队列中的元素是以一定次序单调的，那么push在每次向着队尾放数据的时候，如果队头方向有不符合单调规则的元素，就通通剔除，并且保证队头元素必定是最大值，这时候是队尾出元素。
pop函数，其实就是模拟窗口滑动时数组强制出数据的场景，假如这个时候刚好在原始字符串/数组中是队头的最大值出数据，就把队头删除。（窗口滑动和队头删除不等价，有些注定无用的数据在push的时候为维护队列单调性就已经拿掉了）
getMaxValue函数，获取队头的最大值，每次窗口滑动时都可以求一次当前最大元素

看这个push和pop就能理解为啥要用deque了吧

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

在这里插入图片描述
这道题主要是统计元素频率（用哈希表），然后计算频率数组的前K大数据（排序 or 优先级队列）

由于计算频率数组的前K大数据之前，我们的频率是存在哈希表里的，哈希表是没办法用sort排序的，只能是先转vector，再sort快排；或者转优先级队列

vector+快排

class Solution {
public:static bool Comp(const pair<int,int> &a,const pair<int,int> &b){return a.second > b.second;}vector<int> topKFrequent(vector<int>& nums, int k) {vector<int> res;unordered_map<int,int> FreqMap;for(int i : nums){if(FreqMap.count(i) == 0){FreqMap.insert(pair<int,int>(i,1));}else{FreqMap.find(i)->second++;}            }vector<pair<int,int>> FreqVec;for(auto i : FreqMap){FreqVec.push_back(i);}sort(FreqVec.begin(),FreqVec.end(),Comp);for(auto i : FreqVec){res.push_back(i.first);if(res.size() == k){break;}}return res;}
};

优先级队列

class Solution {
public:typedef struct cmp{bool operator()(pair<int,int> a,pair<int,int> b){return a.second > b.second;} }cmp;vector<int> topKFrequent(vector<int>& nums, int k) {vector<int> res;unordered_map<int,int> Freq_Map;for(int i : nums){if(Freq_Map.find(i) == Freq_Map.end()){Freq_Map.insert(pair<int,int>(i,1));}if(Freq_Map.find(i) != Freq_Map.end()){Freq_Map[i]++;}}priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;int count = 0;for(auto i : Freq_Map){pq.push(i);count++;if(count > k){pq.pop();count--;}}while(!pq.empty()){auto i = pq.top();pq.pop();res.push_back(i.first);}return res;}
};