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

思想很简单：  
1. 构造出一个窗口（用deque，这里不用queue是因为queue没有迭代器不方便操作）  
2. 找出第一个窗口的最大值，记录下来，并压入返回数组  
3. 后续移除首元素，添加下一个元素构成新的窗口。如果前一个窗口的最大值是被移除的首元素则重新找最大值  
4. 不然将前一个窗口的最大值和下一个添加元素比较，得出当前窗口的最大值，覆盖最大值，并压入返回数组  
5. 循环3、4步直到数据集末尾

空间复杂度O(n)
时间复杂度O(n)
实际上额外的空间只有一个窗口大小
如果每次都是首元素最大，则时间复杂度会更高（接近O(n*size)）

class Solution {
public:
    vector<int> maxInWindows(const vector<int>& nums, int size) {
      int i = 0;
      int max = -99999;
      std::deque<int> window;
      std::vector<int> res;
      
      for (; i < size; ++i) {
        window.push_back(nums[i]);
      }
      
      max = find_max(window, window.begin(), window.end());
      res.push_back(max);
      
      //  后面的窗口只需要移除和添加即可
      //  如果最大值被移除则需要重新找
      while (i < nums.size()) {
        if (max == window.front()) {
          max = find_max(window, window.begin() + 1, window.end());
        }
        window.pop_front();
        window.push_back(nums[i++]);
        if (max < *(window.end() - 1)) {
          max = *(window.end() - 1);
        }
        res.push_back(max);
      }
      
      return res;
    }
  private:
    int find_max(std::deque<int> &window, std::deque<int>::iterator fir, std::deque<int>::iterator las) {
      int max = -99999;
       //  第一个窗口
      while (fir != las) {
        if (*fir >= max) {
          max = *fir;
        } 
        ++fir;
      }     
      
      return max;
    }
};
```​