【数据结构】单调队列

参考这篇文章

单调队列的作用是：给定一个长度为 n 的数组，维护长度为 m 的区间最大/小值

（下面以维护区间最小值为例，最大值相反）

简单来说就是维护一个 deque，deque 的队头是当前最小值的序号，其余所有元素都是之后可能成为最小值的元素的序号（只有可能成为最小值，元素的序号才会存在于队中）

时间复杂度 $O(n)$

模板：

deque<int> q; // 存储序号
for (int i = 0; i < n; ++i)
{if (!q.empty() && i - q.front() >= m) // 长度超出的从前开始删，直到删到长度符合要求为止q.pop_front();while (!q.empty() && V[q.back()] > V[i]) // 从队尾开始，凡是比新入队的大的，那它再也不可能成为最小值了，就直接删掉（求区间最大值把这里改成<即可）q.pop_back();q.push_back(i); // 新元素序号入队if (i >= m - 1)cout << V[q.front()] << " ";
}