简洁的滑动窗口实现

algo_h · 2024-12-07 00:56:30 · 算法·理论

维护窗口数据缓冲区和单调队列。基于 STL 的简单实现。

实际上，deque<int>::iterator 的大小可能是 int 的 8 倍，故数据规模较小时，可以考虑在单调队列中存储 int 类型的下标，不清除离开滑动窗口的数据。

另一种可能的优化方案是维护一全局偏移量，初始为 0。每当离开滑动窗口的数据足够多时，删除之并相应增加全局偏移量。每当从单调队列中取得下标后，减去全局偏移量再应用于缓冲区即可。

class SlideWindow {
public:
  SlideWindow(size_t capacity);
  void Push(int value);
  int Max() const;

private:
  size_t capacity;
  deque<int> buffer;
  deque<deque<int>::iterator> window;  // 严格单调递减队列
};

SlideWindow::SlideWindow(size_t c) : capacity(c) { }

void SlideWindow::Push(int value)
{
  auto it = buffer.insert(buffer.end(), value);

  if(!window.empty() && size_t(it - window.front()) == capacity) window.pop_front();
  while(!window.empty() && *window.back() <= value) window.pop_back();
  window.push_back(it);
  buffer.erase(buffer.begin(), window.front());  // 最小化空间占用
}

int SlideWindow::Max() const { return *window.front(); }