239. 滑动窗口最大值
题目链接：239. 滑动窗口最大值
题目描述：给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
```
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
```
思路
本题是迄今为止出现过的难度最大的题目，若使用暴力算法就是遍历一遍的过程中每次从窗口中再找到最大的数值，但是这样的时间复杂度就是O(n × k)。
实在不理想，所以难点。
那么首次出现一个熟悉的数据结构但是未被使用--大顶堆（优先级队列）或者小顶堆。
但是问题是这个窗口是移动的，而大顶堆每次只能弹出最大值，我们无法移除其他数值，这样就造成大顶堆维护的不是滑动窗口里面的数值了。所以不能用大顶堆。
我们需要一个队列，这个队列呢，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。
每次窗口移动的时候，调用que.pop(滑动窗口中移除元素的数值)，que.push(滑动窗口添加元素的数值)，然后que.front()就返回我们要的最大值。
可惜了，！ 我们需要自己实现这么个队列。
其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。
那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。C++中没有直接支持单调队列，需要我们自己来实现一个单调队列
代码实现
239. 滑动窗口最大值
//滑动窗口去遍历
//输出每一次的最大值
本题还是有难度的，重点考察的就是一个单调队列的数据结构
着重完成pop(),push(),getMaxblue(),自定义三个函数.
注意主函数最好还是要写的,只不过这是为了更好的调用
class Solution {
private:
class MyQueue{
public:
deque<int> que;//默认的容器就是deque
pop(int val()){
//即每项后一位就把前面的元素pop传进value
if(que.empty() && val ==que.front){
que.pop_front();//此时队列
上述即pop之前判断队列当前是否为空&&如果pop弹出的元素
等于队列的front，说明pop左边要弹出的元素是一个最大值
}
push(int val()){
while (!que.empty() && value > que.back()) {
que.pop_back();
}
//即当队列为空 && 加入到的元素（back的位置元素）比之前的队列元素
//都大；则弹出队列之前元素
que.push_back(value);
}
// 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
int front() {
return que.front();
}
}};
//开始写主函数:
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k){
MyQueue que;
vector<int> result;//定义一个result集合
for (int i = 0; i < k; i++) { // 先将前k的元素放进队列
que.push(nums[i]);//调用自定义函数:让k的最大值push
}
result.push_back(que.front());
// result 记录前k的元素的最大值
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 个高频元素
题目链接：347.前 K 个高频元素
题目描述： 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
思路
这道题目主要涉及到如下三块内容：
- 要统计元素出现频率
- 对频率排序
- 找出前K个高频元素
首先统计元素出现的频率，这一类的问题可以使用map来进行统计。
然后是对频率进行排序，这里我们可以使用一种 容器适配器就是优先级队列。
什么是优先级队列呢？---其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列
什么是堆？
堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），如果懒得自己实现的话，就直接用priority_queue（优先级队列）就可以了，底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。
那么用哪一种堆？
那么问题来了，定义一个大小为k的大顶堆，在每次移动更新大顶堆的时候，每次弹出都把最大的元素弹出去了，那么怎么保留下来前K个高频元素呢。
而且使用大顶堆就要把所有元素都进行排序，那能不能只排序k个元素呢？
所以我们要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。
代码实现
347.前 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) {
//遍历数组,再用map来统计key和val
for(i = 0; i < nums.size; i++){
map[nums[i]]++;//val默认从0开始，val对应的元素出现一次则加一
}
// 定义一个小顶堆，大小为k，对键值对进行排序--所以自己实现一个comparison的函数（即上方）
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
//遍历map，把map映射为变量it上；it也是一个《key，val》的键值对
for((unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
pri_que.push(*it);//优先级队列que遍历一个就加入que
if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
pri_que.pop();//每次都pop最小的元素，堆留下的都是较大的元素
}
}
// 但是小丁堆的头部都是小频率的元素，大频率都是在堆末，所以要倒序输出
vector<int> result(k);
for (int i = k - 1; i >= 0; i--) {
result[i] = pri_que.top().first;
pri_que.pop();
}
return result;
}
}
栈与队列总结
栈与队列的理论基础
里面提到了灵魂四问：
C++中stack，queue 是容器么？
我们使用的stack，queue是属于那个版本的STL？
我们使用的STL中stack，queue是如何实现的？
stack，queue 提供迭代器来遍历空间么？
相信不仅仅是C++中有这些问题，那么大家使用其他编程语言，也可以考虑一下这四个问题，栈和队列是如何实现的。
栈与队列是我们熟悉的不能再熟悉的数据结构，但它们的底层实现，很多同学都比较模糊，这其实就是基础所在。
可以出一道面试题：栈里面的元素在内存中是连续分布的么？
这个问题有两个陷阱：
陷阱1：栈是容器适配器，底层容器使用不同的容器，导致栈内数据在内存中是不是连续分布。
陷阱2：缺省情况下，默认底层容器是deque，那么deque的在内存中的数据分布是什么样的呢？ 答案是：不连续的，下文也会提到deque。
所以这就是考察候选者基础知识扎不扎实的好问题。
**在栈与队列系列中，我们强调栈与队列的基础，也是很多同学容易忽视的点。
使用抽象程度越高的语言，越容易忽视其底层实现，而C++相对来说是比较接近底层的语言。
我们用栈实现队列，用队列实现栈来掌握的栈与队列的基本操作。
接着，通过括号匹配问题、字符串去重问题、逆波兰表达式问题来系统讲解了栈在系统中的应用，以及使用技巧。
通过求滑动窗口最大值，以及前K个高频元素介绍了两种队列：单调队列和优先级队列，这是特殊场景解决问题的利器，是一定要掌握的。 **
标签：13,窗口,队列,最大值,元素,随想录,pop,que,day From： https://www.cnblogs.com/lijian-allan/p/17216604.html