洛谷 P1440 求m区间内最小值 解题报告

emm 蒟蒻最近刚学单调队列，这是一道单调队列的入门题，然后已经有的题解都是直接讲代码，蒟蒻自己来讲一讲通俗易懂的思路吧。（其实代码很短，核心只有5行，各位不必恐慌）

暴力出奇迹

这题所有人看到题面的第一个反应，肯定是暴力。每次查找前\(m\)个数不就行了？一看数据范围，顿时无语。\(O(n*m)\)暴力完美\(TLE\)。

找到优化的契机

我们观察样例，从中发现了一些规律——在寻找 \(i\) 的前 \(m\) 个数的时候，发现了重复。我们在寻找 \(i-1\) 的前 \(m\) 个数的时候，枚举了区间 \([i-m, i-1]\)。而我们在寻找 \(i\) 的前 \(m\) 个数的时候，又枚举了区间 \([i-m+1, i]\)。也就是说，我们重复枚举了 \(m-1\) 个数，这些数导致了如此高的时间复杂度。

如图（纯鼠标绘画，没有触屏的悲剧）。

单调队列

我们发现，在求min值的过程中，重复遍历了这个数组，导致效率低下。

那么，我们能不能记录下min值呢？我们发现，其实我们要求的区间是固定的。那么我们思考一下，

如果， \(j\) 在某一个区间里面是最小值，在这时，来了一个 \(i\) 。\(i\) 比 \(j\) 来的小，也比 \(j\) 后来（换句话说，\(i\) 比 \(j\) 年轻，又比 \(j\) 优秀），那么 \(j\) 永远不可能成为之后区间里面的 \(min\) 值了！那么，我们可以不用考虑 \(j\)，把 \(j\) 弹出。

那么，我们发现，这是一个 先进先出 的数据结构，很显然，我们使用 队列 来进行操作。

但是，我们还需要考虑一点：队列中每一个元素都要比前面来的优秀，所以，我们还需要维护队列的单调性。

我们就引入了一个新的数据结构：单调队列 \(Monotone-Queue\)

这种数据结构常与 动态规划 算法连用，作用于 状态1D/转移1D 等 动态规划中。在此题中，我们在一端维护单调性，另一端维护时效性。

代码实现

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int a[2000005], que[2000005];
// que数组模拟单调队列的操作

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int head = 1, tail = 0;
    printf("0\n");
    // 一开始，先输出一个0
    for (int i = 1; i <= n-1; i++) {
    while (head <= tail && a[que[tail]] >= a[i]) tail--;
    // 维护单调性
    que[++tail] = i;
    // 入队
    while (head <= tail && que[head] <= i-m) head++;
    // 维护时效性
    printf("%d\n", a[que[head]]);
    // 最后输出队列的head就可以了
    } 
    return 0;
} 

小结

总而言之，单调队列在OI中的应用很少。但是，这是一个很重要的板子。如果你理解透彻了，就把它记忆下来。很多类型动态规划的优化就是基于这个模板的。另外，蒟蒻刚学OI，菜到不行。所以，还请大佬多多指教。

洛谷 P1440 求m区间内最小值 解题报告

原文：https://www.cnblogs.com/ByhBlog/p/11788590.html