Welcome to Rooeye's blog

双端队列解决滑动窗口问题

OJ rooeye 454℃ 0评论

有一个整型数组 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平台测试)

  1. vector<int> slide(vector<int> arr, int n, int w)
  2. {
  3. deque<int> deq;
  4. vector<int> res;
  5. int i;
  6. for(i=0; i<n; i++)
  7. {
  8. if(deq.empty()||arr[i]<=arr[deq.back()])
  9. {
  10. deq.push_back(i);
  11. }
  12. else
  13. {
  14. while(!deq.empty()&&arr[i]>arr[deq.back()])
  15. {
  16. deq.pop_back();
  17. }
  18. deq.push_back(i);
  19. }
  20. if(i-deq.front()>=w)
  21. {
  22. deq.pop_front();
  23. }
  24. if(i>w-2){
  25. res.push_back(arr[deq.front()]);
  26. }
  27. }
  28. return res;
  29. }
来自为知笔记(Wiz)

转载请注明:寻梦人博客 » 双端队列解决滑动窗口问题

喜欢 (0)
发表我的评论
取消评论

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址