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

原创博文，转载请注明出处！

# 题目

# 思路

利用C++中的双端队列保存有可能是滑动窗口最大值的下标，其中队首元素保存当前窗口最大值的下标。当滑动窗口改变时，更新队列。队列更新的规则：（1）新元素依次与队尾元素比较，如果队尾元素小于新元素，则删除队尾元素，直至队列中没有小于新元素的值。（2）更新队首元素，如果队首元素不在新滑动窗口中，则删除队首元素。（3）把每次滑动的数字的下标压入队列

找出数组中大小为3的滑动窗口的最大值，在队列中的下标一列，小括号前面的数字表示数字在数组中的下标。

# 代码

  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

View Code

# 复杂度

O(n)

# 测试用例