太久不复习数据结构，几乎快忘记双端队列这个东西了。。。这道题用双端队列解很自然，且思路也很简单，其他方法做到的复杂度可能思维量就比较大了。参考了Discuss区一位大神的代码，思路很清晰https://leetcode.com/problems/sliding-window-maximum/discuss/65956/My-C%2B%2B-O(n)-deque-based-solution-with-explanation现在我大概梳理一下要点：
假设移动窗口区间为
，我们要把关注点放在
上，如果
，那么接下来窗口滑动时得到的最大值都不再可能是
中的值了。因为在窗口左端到达
之前，最大值都只可能是
我们的思路是构建双端队列，注意，队列中存放元素下标而非元素本身。每次当前位置的元素是否大于队列尾端的下标对应的元素，若大于，则将尾端下标弹出，直至小于或队列为空，将当前位置下标推入队列尾端。这个操作始终保持队列头的下标对应当前窗口中的最大元素。还有一点需要注意的是，我们每次移动窗口都要检查队头的下标是否在窗口内，若否，则将队头元素弹出。
以下是代码：
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> buffer;
vector<int> res;
for(int i=0; i<nums.size();++i)
{
while(!buffer.empty() && nums[i]>=nums[buffer.back()]) buffer.pop_back();
buffer.push_back(i);
if(i>=k-1) res.push_back(nums[buffer.front()]);
if(buffer.front()<= i-k + 1) buffer.pop_front();
}
return res;
}
};
