一、题意
二、思考过程
这是使用 单调队列的经典题目。
**单调队列：**即单调递减或单调递增的队列。
这个队列需要我们自己实现，可以用 deque 放进队列窗口的元素随着窗口的移动，队列一进一出，每次移动之后，队列告诉我们里面最大值是什么：
class MyQueue { public: //滑动窗口中移除的元素数值 void pop(int value) { } //滑动窗口添加的元素数值 void push(int value) { } //返回滑动窗口中的最大值 int front() { return que.front(); } };
pop(value):如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作。push(value):如果push的元素value大于入口元素的值，那么就将队列入口的元素弹出。
保持如上规则，每次窗口移动的时候，只要问 que.front()就可以返回当前窗口的最大值。
class Solution { private: class MyQueue {//单调队列（从大到小） public: deque<int> que;//使用deque来实现单调队列 /* 每次弹出栈的时候，比较当前要弹出的数值是否等于队列出口元 素的数值如果相等则弹出，同时pop之前还要判断队列当前 是否为空 */ void pop(int value) { if(!que.empty()&&value==que.front()) { que.pop_front(); } } /* 如果push的数值大于入口元素的数值，那么就将队列后端的数据弹出 直到push的数值小于队列入口元素的数值为止。 这样就保持了队列里的数值是单调从大到小了。 */ void push(int value) { while(!que.empty()&&value>que.back()) { que.pop_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; for(int i=0;i<k;i++)//记录前k元素放进队列 { que.push(nums[i]); } 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; } };
