单调队列解决滑动窗口问题

题目

给你输入一个数组nums和一个正整数k，有一个大小为k的窗口在nums上从左至右滑动，请你输出每次窗口中k个元素的最大值。

分析

这道题难点在于如何在O(1)时间动态算出每个「窗口」中的最大值，使得整个算法在线性时间完成。

如果减少的这个数恰好是窗口中的最值，就需要遍历所有数重新找新的最值。

想在 O(1) 的时间得出新的最值，需要「单调队列」这种特殊的数据结构来辅助。

单调队列实现

就是一个「队列」，只是使用了一点巧妙的方法，使得队列中的元素全都是单调递增（或递减）的。

#include <deque>
#include <iostream>

using namespace std;

// 必须使用一种数据结构支持在头部和尾部进行插入和删除，很明显 deque 和 list 符合要求。
class MonotonicQueue {
 private:
  deque<int> d;

 public:
  MonotonicQueue() {}
  void push(int n);
  void pop(int n);
  int max();
};

void MonotonicQueue::push(int n) {
  // 要把前面比自己小的元素都删掉
  // 如果每个元素被加入时都执行了该操作，最终单调队列中的元素大小就会保持一个单调递减的顺序
  while (!d.empty() && d.back() < n) {
    d.pop_back();
  }
  // 将n加入尾部
  d.push_back(n);
}

void MonotonicQueue::pop(int n) {
  // 想删除的队头元素n可能已经被「压扁」了，已经不存在了，所以这时候就不用删除了
  if (n == d.front()) {
    d.pop_front();
  }
}

int MonotonicQueue::max() { return d.front(); }

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
  MonotonicQueue w;
  vector<int> res;
  for (int i = 0; i < nums.size(); i++) {
    // 先填满窗口的前k-1个元素
    if (i < k - 1) {
      w.push(nums[i]);
    } else {
      w.push(nums[i]);
      res.push_back(w.max());
      w.pop(nums[i - k + 1]);
    }
  }

  return res;
}

总结

单独看push操作的复杂度确实不是O(1)，但是算法整体的复杂度依然是O(N)线性时间。要这样想，nums中的每个元素最多被push_back和pop_back一次，没有任何多余操作，所以整体的复杂度还是O(N)。

空间复杂度就很简单了，就是窗口的大小O(k)。