【代码随想录算法训练Day13】LeetCode 239. 滑动窗口最大值、LeetCode 347.前K个高频元素
Day13 队列
LeetCode 239.滑动窗口最大值【队列】
本题我们的思想是维护一个新的队列，在加入新元素时把所有在他前面比他更小的元素全部删除，保证队首是滑动窗口内的最大值，只有在滑动窗口滑出时才会将队首的最大值删除，如果加入的是更小的数，那么就暂时加入进来。
class Solution {
private:class MyQueue{public:deque<int> q;void pop(int val){if(!q.empty() && val==q.front())q.pop_front();}void push(int val){while(!q.empty() && val>q.back())q.pop_back();q.push_back(val);}int front(){return q.front();}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue q;vector<int> res;for(int i=0;i<k;i++)q.push(nums[i]);res.push_back(q.front());for(int i=k;i<nums.size();i++){q.pop(nums[i-k]);q.push(nums[i]);res.push_back(q.front());}return res;}
};
LeetCode 347.前K个高频元素【优先队列】
此题的思想是小根堆的实现方式，只不过我们用优先队列来实现，我们把整个元素的次序插入，然后按频次次序从小到大排列，把每次最小的从堆中删除，最后留下K个就是最终的K个高频元素。
class Solution {
public:class cmp{public:bool operator()(const pair<int,int>& a,const pair<int,int>& b){return a.second>b.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>>,cmp> 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> res(k);for(int i=k-1;i>=0;i--){res[i]=pri_que.top().first;pri_que.pop();}return res;}
};
不仅是算法的实现复杂，思路更是要好好研究。