题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
class Solution {
public:
vector<int> maxInWindows(vector<int>& nums, int k) {
deque<int> q;
vector<int> res;
for(int i=0;i<nums.size();i++)
{
//判断队头元素是否出队了
while(q.size()&&i-q.front()+1>k) q.pop_front();
//当前元素比队尾元素大，说明之前的元素都没有用了，直接出队，这样维护了单调性。
while(q.size()&&nums[i]>nums[q.back()]) q.pop_back();
//将当前元素入队
q.push_back(i);
//队头元素就是最大值。
if(i+1>=k) res.push_back(nums[q.front()]);
}
return res;
}
};
思路：
可以用一个双端队列(存的是下标)维护一个滑动窗口，每次先判断队首元素是否出队了，出队了就从滑动窗口中剔除，然后判断要加入的元素是否比队尾元素大，大的话就让队列的元素一直出队，这样的话就可以维护一个单调递减的队列(因为加进来的元素都比队尾元素小)，所以队头元素就是当前滑动窗口的最大值。
总结:求滑动窗口最大值就是维护一个单调递减的队列，队头元素就是当前窗口的最大值。