【代码随想录】刷题Day13

1.deque使用

239. 滑动窗口最大值

deque的介绍在C++语法（12）---- 模拟实现queue和stack_哈里沃克的博客-CSDN博客

其实deque就是一个两头都能进出数据的数据结构，我们之所以使用它就是因为他的结构特点就是两边出，这样我们既可以判断大小，又可以出入数据。那么它的底层实现其实就是一个vector存储指针，指针指向vector，指向的vector中才是存储数据的，那么存储指针的vector主要起到向两边扩容和整体遍历的功能。

1.push的思路：如果前面的数据被push进的数据小，那么我们就要将前面的数据一并移除

2.pop的思路：如果打头的数据是我们要删除的数据，那就删除。如果不是，说明其实在push阶段就已经将其pop掉了

3.其实这样的动态过程可以看作是，每一次的push都是将最大值放在最前面为pop做准备，那么每次比前面小的，说明位置上要晚于大的值，并且滑窗往后走，小的值也会被留下作为判断的一个依据。那么pop其实就是将已经离开滑窗并且在deque是最大的值的数pop走

4.得到最大值，其实就是打头的数据

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

2.优先级队列使用

1.重复值计数问题，我们自然想到可以用map来进行查重和计数

2.前k个值的问题，我们自然想到大堆

3.那么重要的事情其实就是如何比较大小来建立大堆，我们需要写一个仿函数得到大堆，那么我们只需要重新写一个类型less的仿函数，比较的是数的重复次数，所以比较的是pair的second。

4.那么其实实现起来就简单了，首先对nums计数查重，将数据放到map中。再把map中的数据调出进行入堆。由于是大堆。那么我们出来的元素就是最大的元素，那么根据要出去几次就pop几次把pair对应的first值传入ret中，这样我们就得到了想要的数据了。

class Solution {
public:class topless{public:bool operator()(const pair<int,int>& x,const pair<int,int>& y){return x.second<y.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {vector<int> ret;unordered_map<int,int> um;for(auto e:nums)um[e]++;priority_queue<pair<int,int>,vector<pair<int,int>>,topless> pq;for(auto e:um){pq.push(make_pair(e.first,e.second));}for(int i=0;i<k;i++){ret.push_back(pq.top().first);pq.pop();}return ret;}
};