（最近在刷困难题，但是大部分和评论差不多，没有写题解的欲望，这道题，我看评论都是用队列写的，但是不用队列一样能过，所以我分别写下，用队列和不用队列的思路）

题目：
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

题解：

① 用队列

首先，一眼优先队列，但是怎么移动窗口的时候怎么去除左边不需要的值呢，这时候我们可以用 set 来代替优先队列，那么我们怎么防止 set 去重呢，我们可以用 pair，同时存储值和下标，这样就不会去重了，接下来特简单，每次移动窗口，添加右边新增值，去掉左边不需要的值，然后取最大值即可

typedef pair P;
class Solution {
public:set
 temp;vector res;vector maxSlidingWindow(vector& nums, int k) {for(int i = 0; i < k; i++) {temp.insert(make_pair(nums[i], i));}res.push_back(temp.rbegin() -> first);for(int i = k; i < nums.size(); i++) {temp.erase(make_pair(nums[i - k], i - k));  // 去除temp.insert(make_pair(nums[i], i));  添加res.push_back(temp.rbegin() -> first);   // 取范围最大值}return res;}
};

但是这是可以优化的，我们还是可以用优先队列来写，细节是考虑加入值的大小，但这个评论区一堆，我就不细说了，可以看该题的评论区

② 不用队列

首先我看这个数的取值范围 -10 的四次方 到 10 的四次方，感觉肯定可以考虑从这里入手，不然为啥不取更大点的范围

那么我们构建一个数组 data[20005]，这是所有数的取值范围，接下来，我们需要考虑这里面应该存的是什么情况的值，无非两种情况

一. 该窗口当前的情况
二. 整个数组的情况

假如是第一个情况，那么我们可以在数组中存方该范围的各个值的数量，但是这样我们怎样找到最大值呢？遍历?不可能，必超时。用线段树？也不行，复杂度跟上面差不多，没啥意义。

所以我们淘汰第一种情况，接下来考虑第二种情况，那么我们肯定不能只存各个值的数量，这个时候值的位置肯定也很重要，所以我们存的是该值的所有索引（用 vector 存）

那我们怎么利用这个值来进行操作呢，我们可以想到既然我们是要找范围最大值，那么此时所有值中的最大值，一定是它范围内的最大值，第二大的值则是除了最大值存在的范围的其他范围的最大值，那么依次这样下去，直到所有范围的最大值都被确定，这样是不是就有解了

接下来就是具体怎么操作了，我们当前值不能重复覆盖掉以前更大值所在的范围，那么我们可以用 bool 数组来存，是否被之前的更大值覆盖，然后直接跳过被覆盖过就行，每个值都考虑 k 次，这样很简单，但是会超时（亲测）

那这应该怎么办呢，我们就要考虑，我们用 bool 来存，会不会漏了什么信息没有保存，诶对了，我们可以把 bool 改为 int 来存当前位置覆盖到的之后最大位置，这样我们就不用一个个遍历，可以直接跳过了，这样改，就可以在规定时间内跑过了

typedef pair P;
class Solution {
public:int flag1 = 0;int flag2 = 0;vector res;vector ddd[20005];int mmm[100005];int fff[100005] = { 0 };vector maxSlidingWindow(vector& nums, int k) {for(int i = 0; i < nums.size(); i++) {ddd[nums[i] + 10000].push_back(i);flag2 = max(flag2, nums[i] + 10000);}while(flag1 < nums.size()) {while(ddd[flag2].empty()) {flag2--;}int f = ddd[flag2][ddd[flag2].size() - 1];int p = 0;while(p < k && f < nums.size()) {if(fff[f] != 0) {int temp = fff[f];fff[f] = k - p;p = p + temp;f = f + temp;}else{fff[f] = k - p;mmm[f] = flag2 - 10000;p++;f++;flag1++;}}ddd[flag2].pop_back();}for(int i = k - 1; i < nums.size(); i++) {res.push_back(mmm[i]);}return res;}
};