239. 滑动窗口最大值
题目链接：
https://leetcode.cn/problems/sliding-window-maximum/
算法思想
使用队列实现。最简单的思路就是双重循环，时间复杂度是nxk，超时。
可以使用双头队列deque实现。自定义一个双头队列，队列中维护一组单调递减的数据，每次获取最大值，只要获取队头的值即可。
代码：
class Solution {
public:
class max_queue{
private:
deque<int> d;
public:
void pop(int value) {
if (!d.empty() && value == d.front()) {
d.pop_front();
}
}
void push(int val)
{
while(!d.empty() && d.back() < val)
{
// cout<<"d.pop_front:"<<d.front()<<endl;
d.pop_back();
}
d.push_back(val);
// cout<<"d.push_back"<<val<<endl;
}
int get_max_val()
{
return d.front();
}
};
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
max_queue max_q;
int len = nums.size();
vector<int> res;
for(int i=0;i<k;i++)
{
max_q.push(nums[i]);
}
int max_value = max_q.get_max_val();
// cout<<"max_value:"<<max_value<<endl;
res.push_back(max_value);
for(int i=k;i<len;i++)
{
cout<<"i:"<<i<<endl;
max_q.pop(nums[i-k]);
max_q.push(nums[i]);
int max_value = max_q.get_max_val();
// cout<<"max_value:"<<max_value<<endl;
res.push_back(max_value);
}
return res;
}
};
347. 前 K 个高频元素
代码链接：https://leetcode.cn/problems/top-k-frequent-elements/
算法思路：
最前k的最大频率元素。
首先使用map进行频率的统计，
其次，维护一个k个元素的小顶堆。为什么使用小顶堆呢？因为小顶堆pop()的时候，弹出最小元素，最后就留了前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> m;
int len = nums.size();
for(int i=0;i<len;i++)
{
if(m.find(nums[i])==m.end())
m[nums[i]] = 0;
m[nums[i]] += 1;
}
priority_queue<pair<int,int>, vector<pair<int,int>>, mycomparison> pri;
for(unordered_map<int,int>::iterator it = m.begin();it!=m.end();it++)
{
pri.push(*it);
if(pri.size()>k)
{
pri.pop();
}
}
vector<int> result(k);
for(int i=0;i<k;i++)
{
result[i] = pri.top().first;
pri.pop();
}
return result;
}
};
