重庆分公司
重庆分公司，新征程启航
为企业提供网站建设、域名注册、服务器等服务
栈和队列（三）|239.滑动窗口最大值、347.前K个高频元素-创新互联
239. 滑动窗口大值
本文标题：栈和队列（三）|239.滑动窗口最大值、347.前K个高频元素-创新互联
路径分享：http://cqcxhl.com/article/dehdpo.html
题意理解：本题因为要求时间复杂度是线性O(n)，所以不能采用暴力解法O(k*n)，也就是对所有的窗口元素遍历求大值输出。
卡哥采用了自己定义单调栈的方法，实现在滑动窗口移动的pop和push过程中就对栈内元素进行维护，使得栈首永远保存窗口大值。
该栈的实现基于deque，因为它也是queue的底层，而且可以方便地对首端尾端进行删除和填入的操作，便于DIY。
步骤：
定义自己的单调栈和pop，push，front方法
注意pop和push带参数value，这是区别于常规的特点。并且自己的pop和push方法分别是在首端pop，尾端push。
push时，栈尾部比value小，就要被持续地卷走
pop时，栈首若等于value，就被pop掉，否则不需要操作，因为已经在push时被卷走了
front就是获取栈首值，直接返回就好，因为我们在pop和push时已经维护了栈首即为滑动窗口大值
平台调用方法maxSlidingWindow，记得先把前k个值塞进栈里再进入读数组数据的循环。记得实体化声明我们的单调栈
本题关键收获：
实现自己用deque去DIY栈
在栈内进行数据维护
在类内同样可以实现一个类
class Solution {
public:
class myqueue{
public:
dequeque;
void push(int value){
// 新进来的值比栈尾数据大就从尾部弹出
while(!que.empty()&&que.back()maxSlidingWindow(vector& nums, int k) {
myqueue que;
// 把前k个数据先放进栈里,并生成第一个滑动窗口的大值
for(int i=0;ires;
res.push_back(que.front());
// 开始push pop操作，并即时更新滑动窗口大值
for(int i = k;i 题意理解：
首先需要统计各元素出现的频率，用unordered_map是很好的。
其次本题是要求前k个高频元素，所以没必要对所有的map成员进行排序，只需要维护前k个成员即可，这时候用小顶堆很好，而优先级队列priority_queue就是基于小顶堆实现的，小顶堆也是一种二叉树。
最后对维护好的优先级队列转换成vector输出结果，注意顺序
步骤：
统计各元素出现频率
定义优先级队列（排列规则compare函数要自己写）
遍历map成员输入到优先级队列中，并且当队列元素超过k时弹出，小顶堆的顶是小元素
输出到结果vector中
本题收获：
重点掌握小顶堆和优先级队列的应用场景，对于本题只需要维护前k个高频元素的情况很适用
要学会写自己的仿函数compare
学会声明优先级队列
掌握对map元素遍历的方法 ，采用迭代器
class Solution {
public:
// 小顶堆
class mycomparison {
public:
bool operator()(const pair& lhs, const pair& rhs) {
return lhs.second >rhs.second;
}
};
vectortopKFrequent(vector& nums, int k) {
// 统计各元素出现次数
unordered_mapmap;
for(int i=0;i, vector>, mycomparison>que;
for(auto it=map.begin();it!=map.end();it++){
que.push(*it);
if(que.size()>k) que.pop();
}
vectorres(k);
for(int i=k-1;i>=0;i--){
res[i] = que.top().first; // first是属性不是方法
que.pop();
}
return res;
}
}; 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文标题：栈和队列（三）|239.滑动窗口最大值、347.前K个高频元素-创新互联
路径分享：http://cqcxhl.com/article/dehdpo.html