【剑指offer】滑动窗口的最大值，C++实现

  1 #include <iostream>
  2 #include <vector>
  3 #include <queue>
  4 using namespace std;
  5 
  6 class Solution {
  7 public:
  8     vector<int> maxInWindows(const vector<int>& num, unsigned int size)
  9     {
 10         vector<int> res; // 存储每个滑动窗口的最大值
 11         deque<int> s;    // 保存滑动窗口最大值数字的下标
 12 
 13         for(unsigned int i=0;i<num.size();++i)
 14         {
 15             // 更新队列：删除小于新元素的值
 16             while(s.size() && num[s.back()]<=num[i])
 17                 s.pop_back();
 18 
 19             // 更新队列：更新队首元素
 20             if(s.size() && i-s.front()+1>size)
 21                 s.pop_front();
 22 
 23             // 更新队列：新元素的下标加入队列
 24             s.push_back(i);
 25 
 26             // 存储结果
 27             if(size&&i+1>=size)
 28                 res.push_back(num[s.front()]);
 29         }
 30         return res;
 31     }
 32 };
 33 int main()
 34 {
 35     unsigned int size = 3;
 36     const vector<int> num = {1,2,3,4,5,6,7,8,9};
 37 
 38     Solution solution;
 39     solution.maxInWindows(num,size);
 40     return 0;
 41 }
 42