题解 | #滑动窗口的最大值#

#include <deque>
#include <queue>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型vector
     * @param size int整型
     * @return int整型vector
     */
    vector<int> maxInWindows(vector<int>& num, int size) {
      //使用队列存储数组的索引
      if(size == 0){
        return {};
      }
      if(size > num.size()){
        return {};
      }
      vector<int> res;
      deque<int> dq;
      //先遍历第一个窗口
      for(int i= 0;i<size;i++){
        while(!dq.empty() && num[dq.front()] < num[i]){
            dq.pop_back();
        }
        dq.push_back(i);
      }
      res.push_back(num[dq.front()]);

      //继续遍历
      for(int i = size;i<num.size();i++){
        //先去掉队列中不在窗口之中的下标
        while(!dq.empty() && dq.front() < i - size + 1){
            dq.pop_front();
        }

        // 去掉队列中对应元素小于num[i]的下标
        while(!dq.empty() && num[dq.back()] < num[i]){
            dq.pop_back();
        }

        dq.push_back(i);
        res.push_back(num[dq.front()]);
      }
      return res;
    }
};

I got it ! 队列中存储元素下标。先遍历第一个窗口。在遍历后续窗口的过程中，先从队列中移除不在窗口中的元素的下标，然后移除对应元素小于当前元素的下标，然后将当前下标加入队列，并将num[dq.front()]添加到结果集中。