单调队列

引入情景

区间最大值

给你 \(n\) 个数，指定区间的大小 \(m\)，你需要输出每一个大小为 \(m\) 的区间当中的最大值。

初步思考

暴力思想

我们可以非常简单而自然地想到这样一种暴力思想：对于任意一个区间，我们都花费一个 \(\mathcal O(m)\) 的循环去统计这个区间当中的最大值，然后输出。这种方法非常简单粗暴，但是在这道题目当中，\(\mathcal O((n-m+1)m)\approx\mathcal O(nm)\) 的复杂度显然很难满足复杂度。几百几千个数还好，要是量级一旦上了十万，甚至一百万，就会导致我们程序的运行效率大打折扣。

看来，我们需要设计一个更优的算法来解决。

错误思想

很自然地，我们设 \(p_i=\sum\limits_{j=1}^{i}a_j\)，也就是 \(1\sim i\) 当中的最小值，那么查询区间 \([l,r]\) 的时候我们就看一下 \(p_{(l-1)}\) 是否正好等于 \(p_r\)，如果等于的话就说明 \([l,r]\) 的解不可能是 \(p_r\)。这种方法有以下两个致命错误：

• 可能在 \([1,l-1]\) 和 \([l,r]\) 当中的最大值是一样的，也就是说题目没有告诉我们数组当中的数是不一样的；
• 而就算数不一样，那我们也无法求 \([l,r]\) 当中的最大值了，因为最大值都不是它了。

不完全思想

想一想，动态最值问题……这不是可以用 STL 当中的 Priority Queue 优先队列吗？我们就把对顶设为最大的元素，进入队列的同时记录编号。然后查询时我们就将对顶，也就是最大值判断一下，如果超出了当前区间的查询范围，也就说明这个数不是当前区间的了，那么我们就 pop，然后对顶就既是最大的元素、又在区间内的了。而更劣的元素如果它不在区间内的话，我们也完全不需要管它，因为它已经不可能成为最优解了。

每一个元素都最多进队出队一次，那么算法时间复杂度就是 \(\mathcal O(n\log_2 n)\) 的了。但是，这样的复杂度还是不够优秀。万一 \(n\) 有一千万呢？这时候，就需要我们的单调队列了。

算法思想

算法改进

上一个不完全思想的问题所在就是优先队列带来的对数复杂度，而其实我们完全没有必要使用优先队列，我们可以自己维护一个有顺序的队列。这个队列的不同之处就是加入当前元素的时候，我们需要将队列尾更劣的元素弹出，因为它们不但比当前元素小，而且还在当前元素的前面，那么它们就对最优解没有贡献了。弹出之后再加入当前元素，就可以维护这个单调的队列了。

复杂度

这种算法免去了对数的复杂度，就是 \(\mathcal O(n)\) 的。由于我们额外维护了一个队列，那么空间复杂度就是 \(\mathcal O(n)\) 的。

注意

单调队列并非普通的队列，除了支持尾部插入和头部访问删除以外，我们还要实现尾部访问删除。不过由于没有头部插入，其实操作起来跟普通队列没有过大的区别，只需要移动尾指针就行了。若要使用 STL 的话，建议使用 list 双向链表 这个容器。

代码

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    for (; q.size() && i - m >= q.front(); q.pop_front()) { }
    for (; q.size() && a[q.back()] <= a[i]; q.pop_back()) { }
    q.push_back(i);
    if (i >= m) {
      cout << a[q.front()] << ' ';
    }
  }
  return 0;
}

评论