Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1878372
  • 博文数量: 184
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2388
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(184)

文章存档

2021年(26)

2020年(56)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: C/C++

2021-03-20 16:53:02

单调队列,保证当前队列的头元素是最大的(后面的可以<=当前的头元素),移除窗口元素时,比较是否跟队列头相等即可

点击(此处)折叠或打开

  1. vector<int> maxSlidingWindow(vector<int>& nums, int k){
  2.     vector<int> res;
  3.     deque<int> q;
  4.     int len = nums.size();
  5.     if(len ==0) return res;
  6.     for(int i=0;i<len;++i){
  7.         for(;i>0&&q.size()>0&&nums[i]>q.back();) q.pop_back();
  8.         q.push_back(nums[i]);
  9.         if(i>=k &&nums[i-k]==q.front()) q.pop_front();
  10.         if(i >=k-1) res.push_back(q.front());
  11.     }
  12.     return res;
  13. }

阅读(860) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~