有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边,窗口每次向右边滑一个位置。 返回一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。 以数组为[4,3,5,4,3,3,6,7]，w=3为例。因为第一个窗口[4,3,5]的最大值为5，第二个窗口[3,5,4]的最大值为5，第三个窗口[5,4,3]的最大值为5。第四个窗口[4,3,3]的最大值为4。第五个窗口[3,3,6]的最大值为6。第六个窗口[3,6,7]的最大值为7。所以最终返回[5,5,5,4,6,7]。给定整形数组arr及它的大小n，同时给定w，请返回res数组。保证w小于等于n，同时保证数组大小小于等于500。
测试样例： [4,3,5,4,3,3,6,7],8,3 返回：[5,5,5,4,6,7]
普通解法可以对每个窗口循环判断求每个窗口的最大值，但是时间复杂度需要O(n*w)，使用双端队列deque的方法可以在O(n)时间复杂度内解决。
主要思路如下：
循环遍历arr，使用res存储返回结果，假设当遍历arr[i]的时候，deque队尾为j，deque队头为k：
1. 如果deque为空（j，k不存在），将i(注意不是arr[i])的值从deque队尾压入；
2. 如果arr[i] <= arr[j]，将i从deque队尾压入；
3. 如果arr[i] > arr[j] , 不断弹出队尾元素，直到arr[i]小于等于arr[j]或者deque为空，再将i从deque的队尾压入；
4. 上述3步可以保证与deque中元素对应的arr的值恒为递减序列；
5. 如果 j-k >= w，说明deque的队头元素已经过期，将deque的队头元素弹出即可；
6. 在从队头弹出过期元素后，此时deque的队头元素所对应的arr的值即为当前窗口的真正的最大值，将arr[deq.front()]压入res即可；
7. 重复执行上述步骤，直到arr遍历结束，res即为所求结果。
c++代码：（已通过oj平台测试）
vector<int> slide(vector<int> arr, int n, int w){deque<int> deq;vector<int> res;int i;for(i=0; i<n; i++){if(deq.empty()||arr[i]<=arr[deq.back()]){deq.push_back(i);}else{while(!deq.empty()&&arr[i]>arr[deq.back()]){deq.pop_back();}deq.push_back(i);}if(i-deq.front()>=w){deq.pop_front();}if(i>w-2){res.push_back(arr[deq.front()]);}}return res;}
转载请注明：晋坤 的博客 » 双端队列解决滑动窗口问题
