力扣239题 滑动窗口最大值
设计单调队列的时候，pop和push操作要保持如下规则：
1.pop(value):如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
2.push(value):如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止。
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();} };
完整的代码逻辑：
class Solution {
public:
class MyQueue{
public:
deque<int>que;
void pop(int value){
if(!que.empty()&&value == que.front()){
que.pop_front();
}
}
void push(int value){
while(!que.empty()&&value > que.back()){
que.pop_back();
}
que.push_back(value);
}
int front(){
return que.front();
}
};
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MyQueue que;
vector<int>result;
for(int i=0;i<k;i++){
que.push(nums[i]);
}
result.push_back(que.front());
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个高频元素
这道题目主要涉及到如下三块内容
1.要统计元素出现频率
2.对频率排序
3.找出前k个高频元素
优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方法，看起来就是一个队列。
堆是一颗完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
只排序k个元素，要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。
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;
for(int i=0;i<nums.size();i++){
map[nums[i]];
}
priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparison>pri_que;
for(unordered_map<int,int>::iterator it = map.begin();it !=map.end();it++){
pri_que.push(*it);
if(pri_que.size()>k){
pri_que.pop();
}
}
vector<int>result(k);
for(int i=k-1;i>=0;i--){
result[i] = pri_que.top().first;
pri_que.pop();
}
return result;
}
};