有一个整型数组 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;
}
转载请注明:晋坤 的博客 » 双端队列解决滑动窗口问题