单调队列思想：滑动窗口、极值维护与均摊优化

在做题时，我们经常会遇到这样一类要求：给一个序列，一个固定长度的窗口从左往右滑动，每滑一格，就得报出当前窗口里的最大值或者最小值。

先别急着背数据结构模板。我们先想想，最容易想到的办法是怎么做的？无非是窗口每挪动一格，就把这 k 个数从头到尾扫一遍。每个窗口花 $O(k)$ ，合起来就是常说的 $O(nk)$ 。n、k 一大，反复扫描就吃不消了。

但只要你稍微停下来观察一下窗口的滑动过程，就会发现这里面有大量的无用功。窗口向右滑一格，实际上只发生两件事：最左边出去了一个老元素，最右边进来了一个新元素。中间绝大部分的数根本没变。暴力算法之所以慢，就是因为反复在看这些没变过的数。

那我们能不能在移动的过程中，把那些“已经被新来的数比下去”的旧候选提前剔除掉？

一、旧元素为什么能直接扔掉？

假设现在窗口里有两个位置 $x$ 和 $y$ ，其中 $x$ 排在 $y$ 的左边（ $x < y$ ）。如果在数值上满足 $a[x] \le a[y]$ ，我们来问一个简单的问题：

在接下来的滑动过程中， $a[x]$ 还有保留的必要吗？

如果只关心最大值，就没有必要。理由很直白：第一，看数值大小：新来的 $a[y]$ 至少和 $a[x]$ 一样大；第二，看存活时间：因为 $x$ 在左边、 $y$ 在右边，窗口往右滑时， $x$ 一定比 $y$ 更早滑出窗口离开。

只要 $x$ 还在窗口里， $y$ 就必定也在，而且 $a[y]$ 不比 $a[x]$ 小；等 $x$ 滑出了窗口， $x$ 就更没用了。一句话说透：新来的至少一样大，还走得更晚，旧的可以放心让位。

保留 $y$ 就已经足够代表这两个候选，直接删掉 $x$ ，丝毫不会改变后续求最大值的答案。把这些可以被替代的旧元素全部踢掉，剩下那些还在等待机会的元素就会自然排成一个“单调递减”的序列。这就是单调队列的全部出发点。

二、队列的维护机制与手推过程

1. 为什么队列里要存下标？

在实现单调队列时，我们使用 std::deque<int>（双端队列），而且队列里存的是数组的下标，而不是数值本身。

原因很简单：当窗口滑动时，我们需要判断队首元素是不是已经“过期”（滑出了当前窗口的左边界）。如果我们只存数值，就无法知道这个数当前到底位于哪个位置；而如果存了下标 $i$ ，我们既能用 $a[i]$ 拿到数值去比大小，又能通过下标直接算出来它有没有过期。

2. 相等值怎么处理？

当新来的元素和队尾元素数值相等时，我们要不要把队尾弹掉？假设求最大值，新来的 $a[i]$ 等于队尾的 $a[q.back()]$ 。新元素数值没输，但它的下标更新、能在窗口里多活几轮。因此，把旧的队尾弹掉、换上新下标，对最大值没有任何损失，反而延长了该数值的有效生命期。所以在比对时，我们通常写 a[q.back()] <= a[i]。这样能保证队列内部数值呈现严格单调递减。

这里讨论的是最值本身。如果题目还要求最早出现的位置或最优方案数，就得重新考虑相等候选能不能删，不能把这个条件原封不动套过去。

3. 一步一步手推演示

我们取一组具体数据： $a = [4, 2, 2, 5, 1, 3]$ ，窗口大小 $k = 3$ ，目标是求每个完整窗口的最大值。当前遍历位置为 $i$ ，完整窗口区间是 $[i - k + 1, i]$ ；在 $i < k$ 时，窗口尚未凑满。

我们用 (下标:数值) 来记录队列内部状态：

i 及新值	本轮关键操作	队列（下标:值）	当前最大值
1： $a[1]=4$	队空，直接入队	`[(1:4)]`	窗口未满
2： $a[2]=2$	尾部 $a[1]=4 > 2$ 不淘汰，(2:2) 入队	`[(1:4), (2:2)]`	窗口未满
3： $a[3]=2$	尾部 $a[2] \le 2$ 淘汰 (2:2)，(3:2) 入队	`[(1:4), (3:2)]`	4
4： $a[4]=5$	队首 1 已过期弹出；尾部 $a[3] \le 5$ 淘汰；(4:5) 入队	`[(4:5)]`	5
5： $a[5]=1$	尾部 $a[4]=5 > 1$ 不淘汰，(5:1) 入队	`[(4:5), (5:1)]`	5
6： $a[6]=3$	尾部 $a[5] \le 3$ 淘汰 (5:1)，(6:3) 入队	`[(4:5), (6:3)]`	5

看 $i = 4$ 这一步：

窗口左边界变成了 $4 - 3 + 1 = 2$ 。此时队首下标是 1，比 2 小，说明它已经滑出窗口了，必须从队首弹出（pop_front()）。
接着新元素 $a[4] = 5$ 准备入队，发现队尾的 $a[3] = 2 \le 5$ ，旧元素既小又老，从队尾弹出（pop_back()）。
最后把 4 号下标推进去。此时队首存的下标就对应整个窗口的最大值。

滑动窗口最大值最终依次是：4, 5, 5, 5。如果求最小值，只需要把队尾淘汰条件改成 a[q.back()] >= a[i]，得到的结果就是：2, 2, 1, 1。

4. 固定窗口模板的四步走

先把本节固定窗口模板的顺序记清楚，后面遇到前缀和、DP 时，再根据候选范围调整，不能只抄顺序不看含义。

清队首过期：只要队列非空且 q.front() < i - k + 1，就执行 q.pop_front()，直到队首不过期或队空；
清队尾劣解：只要队列非空且新元素至少一样优（求最大值时满足 a[q.back()] <= a[i]），就循环执行 q.pop_back()；
新元素进队：将当前下标推入队尾 q.push_back(i)；
取当前答案：当 $i \ge k$ 时，说明窗口已经完整进入数组，此时 a[q.front()] 就是当前窗口的最大值。

换一个求最小值的例子：[1,4,3,2]，窗口长度为 3。处理位置 4 时，先从队首去掉过期的下标 1，再从队尾去掉不如新数 2 的下标 3，最后让下标 4 入队。

单调队列维护滑动窗口最小值的流程

三、为什么它快？复杂度与工具选型

代码里外层一个 for，内层还有 while，它真的比暴力快吗？

我们换个视角看：整个扫描过程中，每一个下标 $i$ （从 $1$ 到 $n$ ）都只会被推进去一次（push_back 一次）。而进过队列的元素，要么从队首因为过期弹出来一次，要么从队尾被淘汰弹出来一次，绝不可能死而复生。也就是说，所有入队操作总共只有 $n$ 次，所有出队操作的总和也绝不会超过 $n$ 次。

别盯着某一轮的 while 看，把整趟扫描合起来算：每个下标进一次、最多出一次，总时间就是 $O(n)$ 。本讲还存了原数组，整体空间为 $O(n)$ ；队列本身最多装 k 个下标。

但单调队列并不是万能钥匙。我们需要把它和手头的其他工具分清楚：

单调栈：只能从栈顶操作。它适合找“某元素左边/右边第一个比它大的数”。但如果加上“窗口长度不能超过 $k$ ”的限制，就还需要淘汰窗口左边过期的候选，单靠栈顶的操作不够。
单调队列：这里用双端队列实现，从队尾加入、从两端删除。适合处理窗口左右端点“只往前走、不往后退”的区间最值问题。如果查询区间是乱序跳跃的（比如一会儿查 $[2, 5]$ ，一会儿查 $[1, 3]$ ），已经删掉的候选无法找回，这套维护方式就不能直接用了。
ST 表：常规做法对静态数组进行 $O(n\log n)$ 的预处理，之后可以按任意顺序查询区间最值，单次 $O(1)$ 。如果原数组的值发生修改，预处理结果就可能失效，需要重新维护。它和单调队列适用的条件不同，不是谁把谁完全替代。

四、模板实战：洛谷 P1886 滑动窗口

我们来看洛谷官方模板题 P1886 滑动窗口 /【模板】单调队列。题目给出长度为 $n$ 的序列和窗口大小 $k$ （ $1 \le k \le n \le 10^6$ ），第一行输出所有窗口的最小值，第二行输出最大值。

完整程序：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000005;

int a[N];
int n,k;

void getmin(){
    deque<int> q;
    for(int i=1;i<=n;i++){
        while(!q.empty() && q.front()<i-k+1) q.pop_front();
        while(!q.empty() && a[q.back()]>=a[i]) q.pop_back();
        q.push_back(i);
        if(i>=k){
            cout<<a[q.front()]<<(i==n?"\n":" ");
        }
    }
}

void getmax(){
    deque<int> q;
    for(int i=1;i<=n;i++){
        while(!q.empty() && q.front()<i-k+1) q.pop_front();
        while(!q.empty() && a[q.back()]<=a[i]) q.pop_back();
        q.push_back(i);
        if(i>=k){
            cout<<a[q.front()]<<(i==n?"\n":" ");
        }
    }
}

void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    getmin();
    getmax();
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    solve();
    return 0;
}

五、前缀和转化：洛谷 P1714 切蛋糕

很多题表面上看不出“滑动窗口”四个字，但只要把式子一变，单调队列就会浮出水面。

P1714 切蛋糕要求我们在长度为 $n$ 的序列里，找到一段长度不超过 $m$ 的非空连续子段，使得子段和最大（ $1 \le m \le n \le 5 \times 10^5$ ）。

1. 式子怎么变？

遇到连续子段和，首先想到前缀和。设 $s[i] = \sum_{p=1}^i a[p]$ ，并且规定 $s[0] = 0$ 。那么一段区间 $(j, i]$ （也就是下标从 $j+1$ 到 $i$ ）的和就是：

s[i] - s[j]

题目要求子段长度不超过 $m$ 且非空，意味着：

1 \le i - j \le m \implies i - m \le j \le i - 1

因为前缀和下标不能为负，所以 $j$ 真实的取值范围是 $[\max(0, i-m), i-1]$ 。

当我们枚举右端点 $i$ 时， $s[i]$ 是一个定值。要让 $s[i] - s[j]$ 最大，就是要找范围内最小的 $s[j]$ ：

\max_j(s[i] - s[j]) = s[i] - \min_j s[j]

其中 $j$ 均在上述合法范围内。随着 $i$ 往右走， $j$ 的可选范围 $[\max(0, i-m), i-1]$ 也在同步向右移。这不就是维护前缀和数组 $s$ 在滑动窗口下的最小值吗？

2. 时序陷阱：先算答案，还是先进队？

这里有个初学者非常容易错的地方：顺序不能照抄 P1886。

在 P1886 里， $a[i]$ 就在当前窗口里面，所以是先入队、再查队首。但在切蛋糕里，我们要选的子段必须非空！如果当前位置是 $i$ ，前缀下标 $j$ 最大只能取到 $i - 1$ 。如果允许 $j = i$ ，那子段长度就是 0 了。所以每轮循环处理 $i$ 时：

先清掉队首过期的 $j$ （即 $j < i - m$ ）；
先用当前的 $s[i]$ 减去队首的最小 $s[q.front()]$ ，尝试更新全局答案；
然后再把当前的下标 $i$ 作为未来后续位置的候选前缀下标放进队列。

还有两个关键细节：

循环开始前，必须先把下标 0 放进队列（q.push_back(0)）。因为从第 1 个数开始选到第 $i$ 个数也是合法方案，这时要减去的前缀和就是 $s[0] = 0$ 。如果不放 0，你就漏掉了从头开始的子段；这份代码在第一轮还会访问空队列。
原数组元素可能全是负数。全负数时答案也是负数，因此不能把答案初始化为 0。代码先定义一个足够大的正数 const int INF=4000000000000000000LL;，再令 ans=-INF。

每轮查询前，下标 $i-1$ 已经在上一轮入队（第一轮则有下标 0），而 $m\ge1$ 保证它尚未过期，因此这里查询时队列一定非空。

该算法时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。

完整程序：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500005;
const int INF=4000000000000000000LL;

int a[N],s[N];
int n,m;

void solve(){
    cin>>n>>m;
    s[0]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    
    deque<int> q;
    q.push_back(0); // 必须放入前缀和0作为候选左端点
    int ans=-INF;
    
    for(int i=1;i<=n;i++){
        while(!q.empty() && q.front()<i-m) q.pop_front();
        ans=max(ans,s[i]-s[q.front()]);
        while(!q.empty() && s[q.back()]>=s[i]) q.pop_back();
        q.push_back(i);
    }
    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    solve();
    return 0;
}

六、动态规划状态优化：洛谷 P1725 琪露诺

现在我们更进一步，看单调队列如何接管动态规划的转移瓶颈。

在 P1725 琪露诺中，编号为 $0 \dots n$ 的格子上有点数 $a[i]$ （ $a[0]=0$ ）。从 0 号位置出发，每次只能向右跳 $[l, r]$ 之间的距离。跳到某个格子就能拿走对应的点数。一旦跳出的位置超过 $n$ ，游戏结束。求最多能拿多少分。

1. 寻找瓶颈

设 $f[i]$ 表示从起点跳到格子 $i$ 时的最大累计得分。能一步跳到 $i$ 的前驱格子 $j$ ，必须满足跳跃距离在 $[l, r]$ 之间：

l \le i - j \le r \implies i - r \le j \le i - l

由于格子编号非负，所以 $j$ 的实际完整合法范围是：

\max(0, i-r) \le j \le i-l

状态转移方程自然就是：

f[i] = \max_{i-r\le j\le i-l} f[j] + a[i]

这里当然只从编号非负、已经能走到的格子 j 转移；没有这样的前驱，i 就暂时走不到。

如果不做优化，每次算一个 $f[i]$ 都要回过头把这最长为 $r - l + 1$ 的区间扫一遍，整体时间上界是 $O(n(r-l+1))$ ，最坏达到 $O(n^2)$ 。但仔细看前驱区间：当 $i$ 往右挪一位变成 $i+1$ 时，前驱区间变成了 $[\max(0, i+1-r), i+1-l]$ ，两个端点都只会向右推进。这就是滑动区间求最大值。

2. 这里的队列有什么不同？

相比基础滑动窗口，这道题有两个必须扣准的环节：

第一，候选人的“解锁时间”变了。 在计算 $f[i]$ 时，最新的合法前驱是 $i - l$ ，因为从它跳到 $i$ ，距离刚好达到下限 $l$ 。如果 $l=1$ ，它恰好就是 $i-1$ ；如果 $l>1$ ， $i-1$ 离得太近，就不能一步跳到 $i$ 。所以当循环走到 $i$ 时，新解锁、被允许进入候选池的格子是 $i-l$ ，不是当前格子 $i$ 。

第二，不可达状态的隔离。 有的格子可能因为步长限制根本踩不到（比如 $l=3, r=5$ 时，格子 1 和 2 根本跳不到）。我们规定起点 $f[0] = 0$ ，其余所有位置的初始状态全部置为负无穷 -INF。 走不到的格子，就不塞进队列。新候选 $cur = i - l$ 入队前，先看一眼它到底能不能到达（f[cur] != -INF）。只有走得到的位置，才有资格进队。如果队列空了，说明没有任何合法前驱能跳到当前位置 $i$ ，此时不访问队首、不进行转移，让 $f[i]$ 继续保持 -INF。这样也避免了对代表不可达的哨兵值继续加分。

3. 终局怎么算？

题目要求跳过 $n$ 就算结束。官方数据保证 $r \le n$ ，所以不需要考虑从 0 一步越过 $n$ 。站在哪些位置上可以一步跳出 $n$ 呢？只要 $i + r > n$ ，再跳一次长度为 $r$ 的合法步长就能越过终点。所以我们在所有能够一步跳出 $n$ 的可达格子里，找最大的 $f[i]$ 即可。跳到 $n$ 本身还没有结束，它仍然是一个有分数的格子。

算法时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。

完整程序：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
const int INF=4000000000000000000LL;

int a[N],f[N];
int n,l,r;

void solve(){
    cin>>n>>l>>r;
    for(int i=0;i<=n;i++) cin>>a[i];
    
    for(int i=1;i<=n;i++) f[i]=-INF;
    f[0]=0;
    
    deque<int> q;
    
    for(int i=l;i<=n;i++){
        int cur=i-l;
        if(f[cur]!=-INF){
            while(!q.empty() && f[q.back()]<=f[cur]) q.pop_back();
            q.push_back(cur);
        }
        
        while(!q.empty() && q.front()<i-r) q.pop_front();
        
        if(!q.empty()){
            f[i]=f[q.front()]+a[i];
        }
    }
    
    int ans=-INF;
    for(int i=0;i<=n;i++){
        if(i+r>n && f[i]!=-INF){
            ans=max(ans,f[i]);
        }
    }
    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    solve();
    return 0;
}

七、二维网格上的切片扫描：洛谷 P2216 理想的正方形

如果滑动区间变成了一个二维的方块，怎么做？

在 P2216 [HAOI2007] 理想的正方形中，给出一个 $a \times b$ 的整数矩阵，要求在里面找一个 $n \times n$ 的正方形区域，使得这个区域内最大值与最小值的差值最小（ $2 \le a, b \le 1000$ ， $1\le n \le \min(a, b, 100)$ ）。

1. 从一个小例子看拆解方法

我们先拿一个具体的小矩阵来说明：

\begin{pmatrix} 4 & 8 & 2 \\ 6 & 1 & 7 \\ 3 & 5 & 9 \end{pmatrix}

设要求边长 $n = 2$ 的正方形。

先不要试图一步跨到二维。我们先对每一行单独做一次长度为 2 的横向滑动窗口：

第 1 行： $[4, 8]$ 最大是 8， $[8, 2]$ 最大是 8；
第 2 行： $[6, 1]$ 最大是 6， $[1, 7]$ 最大是 7；
第 3 行： $[3, 5]$ 最大是 5， $[5, 9]$ 最大是 9。

这些横向结果另存到 mx，最小值则存到 mn，原矩阵 v 不变。具体来说，mx[i][j] 表示原矩阵第 $i$ 行、以第 $j$ 列结尾的连续 $n$ 格的最大值，也就是列区间 $[j-n+1,j]$ 的最大值；mn[i][j] 存同一区间的最小值。

现在看横向结果 mx 的第 3 列，不是原矩阵的第 3 列。它存着每行最后两格的最大值，从上到下依次是 $[8, 7, 9]$ 。如果我们想求右下角那个 $2 \times 2$ 正方形（即涵盖第 2、3 行，第 2、3 列）的最大值，其实只要在这一列里，把第 2 行和第 3 行的行最大值取一个最大值：

\max(7, 9) = 9

同样的方法处理最小值：第 2 行最后两格的最小值是 1，第 3 行最后两格的最小值是 5；纵向合并得到该区域的最小值是 $\min(1, 5) = 1$ 。两者做差： $9 - 1 = 8$ 。注意：这只是右下角这一块的差值，整张图的最优解还要综合比较其他所有可能摆放的正方形。

但这个过程告诉我们：先横向把每一行的滑动最值压出来，再基于第一步算出的结果纵向扫一遍，正方形的最值就自然出来了。

2. 空间精简实现

在代码里，我们只需要开原矩阵 v，以及存横向结果的 mx 和 mn。在第二趟纵向扫描时，我们一边用单调队列求出当前正方形的极值，一边直接顺手更新全局答案 ans，完全不需要再开额外的二维数组去存最终结果。

别让下标绕晕自己：固定第 $j$ 列，纵向扫描到第 $i$ 行时，我们合并的是 $[i-n+1,i]$ 这 $n$ 行；每一行的横向结果又覆盖 $[j-n+1,j]$ 这 $n$ 列。合在一起，就是原矩阵中以 $(i,j)$ 为右下角的 $n\times n$ 正方形。只有 $i\ge n$ 且 $j\ge n$ ，这个正方形才完整。

整个算法的时间复杂度是 $O(ab)$ ，空间复杂度是 $O(ab)$ 。

完整程序：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;
const int INF=4000000000000000000LL;

int v[N][N];
int mx[N][N],mn[N][N];
int a,b,n;

void solve(){
    cin>>a>>b>>n;
    for(int i=1;i<=a;i++){
        for(int j=1;j<=b;j++){
            cin>>v[i][j];
        }
    }
    
    // 第一趟：逐行横向滑动窗口，求出每行长为n的区间极值
    for(int i=1;i<=a;i++){
        deque<int> q1,q2;
        for(int j=1;j<=b;j++){
            while(!q1.empty() && q1.front()<j-n+1) q1.pop_front();
            while(!q1.empty() && v[i][q1.back()]<=v[i][j]) q1.pop_back();
            q1.push_back(j);
            if(j>=n) mx[i][j]=v[i][q1.front()];
            
            while(!q2.empty() && q2.front()<j-n+1) q2.pop_front();
            while(!q2.empty() && v[i][q2.back()]>=v[i][j]) q2.pop_back();
            q2.push_back(j);
            if(j>=n) mn[i][j]=v[i][q2.front()];
        }
    }
    
    // 第二趟：逐列纵向滑动窗口，基于横向结果直接合并正方形极值并刷新答案
    int ans=INF;
    for(int j=n;j<=b;j++){
        deque<int> q1,q2;
        for(int i=1;i<=a;i++){
            while(!q1.empty() && q1.front()<i-n+1) q1.pop_front();
            while(!q1.empty() && mx[q1.back()][j]<=mx[i][j]) q1.pop_back();
            q1.push_back(i);
            
            while(!q2.empty() && q2.front()<i-n+1) q2.pop_front();
            while(!q2.empty() && mn[q2.back()][j]>=mn[i][j]) q2.pop_back();
            q2.push_back(i);
            
            if(i>=n){
                ans=min(ans,mx[q1.front()][j]-mn[q2.front()][j]);
            }
        }
    }
    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    solve();
    return 0;
}

八、选学：双指针与双队列维护动态变长窗口

前面我们做的滑动窗口长度都是固定的（或者最大长度固定），但有时候，窗口的长度是根据内容动态伸缩的。

问题场景：给定一个长度为 $n$ 的数组，找出一个最长的连续子数组，使得这个子数组内的“最大值减去最小值”不超过给定的 $K$ 。

1. 为什么能用双指针？

随着右端点 $R$ 向右移动，如果我们固定 $R$ ，不断往左边扩大窗口，窗口内的最大值只会变大或不变，最小值只会变小或不变。这就意味着，极差（最大值减最小值）是单调递增的。

一旦某个窗口 $[L, R]$ 的极差超过了 $K$ ，那么对于当前的 $R$ 来说， $L$ 再往左退也没有意义（极差只会更大）。为了让极差降回 $K$ 以内，左端点 $L$ 必须且只能向右收缩。这就是典型的双指针单调性。

2. 双队列协同配合

此时窗口区间是 $[L, R]$ ，左右端点都在向右走。我们要随时知道这个变长窗口里的最大值和最小值，这就可以派出两个单调队列：

一个维护窗口内最大值的单调递减队列 q_max
一个维护窗口内最小值的单调递增队列 q_min

随着 $R$ 向右移动，新元素 $a[R]$ 按标准流程分别进入这两个队列。进队后，当前窗口的最大值就是 a[q_max.front()]，最小值就是 a[q_min.front()]。如果发现 a[q_max.front()] - a[q_min.front()] > K，说明当前区间不合法。我们就要让 $L$ 向右走（L++），直到重新合法为止。在 $L$ 往右走的过程中，如果队首保存的下标刚好等于了原来的 $L$ （说明队首元素随着 $L$ 的右移被踢出窗口了），我们就把它弹出。

3. 一步一步手推演示

假设数组为 $a = [8, 2, 4, 7]$ ，限制极差不超过 $K = 3$ 。

R=1 (a[1]=8)：q_max=[(1:8)], q_min=[(1:8)]。极差 $8-8=0 \le 3$ ，合法，最长记录更新为 1。
R=2 (a[2]=2)：q_max=[(1:8), (2:2)], q_min=[(2:2)] (老元素 8 被淘汰)。此时队首极差 $8-2=6 > 3$ ，不合法！开始收缩： $L$ 从 1 变成 2。此时原来的 1 号元素滑出，q_max 的队首 1 被弹出。收缩后 $L=2$ ，两队列队首都是 2 号元素，极差 $2-2=0 \le 3$ ，合法。
R=3 (a[3]=4)：q_max=[(3:4)] (老元素 2 被淘汰), q_min=[(2:2), (3:4)]。此时队首最大是 4，最小是 2。极差 $4-2=2 \le 3$ ，合法！最长记录更新为 2。
R=4 (a[4]=7)：q_max=[(4:7)] (老元素 4 被淘汰), q_min=[(2:2), (3:4), (4:7)]。极差 $7-2=5 > 3$ ，不合法！收缩： $L$ 变 3，2 号元素滑出窗口，q_min 队首 2 弹出。当前最大 7，最小 4。极差 $7-4=3 \le 3$ ，合法！此时窗口为 $[3,4]$ ，长度为 2。

4. 动态变长窗口代码实现

// 问题：求最大值与最小值之差不超过 K 的最长连续子数组长度
// 输入：n, K，接着 n 个整数
// 范围：1 <= n <= 100000, K >= 0
// 样例输入：
// 4 3
// 8 2 4 7
// 样例输出：
// 2
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;

int a[N];
int n,k_val;

void solve(){
    cin>>n>>k_val;
    for(int i=1;i<=n;i++) cin>>a[i];
    
    deque<int> q_max, q_min;
    int L = 1;
    int ans = 0;
    
    for(int R=1;R<=n;R++){
        // 1. 新元素进双队列
        while(!q_max.empty() && a[q_max.back()]<=a[R]) q_max.pop_back();
        q_max.push_back(R);
        
        while(!q_min.empty() && a[q_min.back()]>=a[R]) q_min.pop_back();
        q_min.push_back(R);
        
        // 2. 检查极差，收缩左边界 L
        while(!q_max.empty() && !q_min.empty() && a[q_max.front()]-a[q_min.front()] > k_val){
            if(q_max.front() == L) q_max.pop_front();
            if(q_min.front() == L) q_min.pop_front();
            L++;
        }
        
        // 3. 统计最长合法区间
        ans = max(ans, R - L + 1);
    }
    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    solve();
    return 0;
}

九、通用提炼：由 DP 式子识别单调队列

当状态转移方程稍微复杂一点时，怎么判断能不能用单调队列？怎么确定队列里面该装什么、什么时候弹？记住这三个问题，你可以直接对着式子把单调队列的代码“翻译”出来。

1. 拆分式子，分离变量

把你的转移方程化简成这样的形式（以求最大值为例）：

f(i) = \max_{L(i) \le j \le R(i)} \{ g(j) \} + h(i)

$h(i)$ ：只和当前位置 $i$ 有关、和前驱 $j$ 无关的项（比如前面琪露诺那题的 $a[i]$ ）。把它扔到求最值的外面，最后加上去就行。
$g(j)$ ：你要评估的“候选人战斗力”。它可能只含有 $f[j]$ ，也可能包含和 $j$ 相关的其他常数项。在队列比较优劣时，我们比较的正是 $g(j)$ 。
$L(i), R(i)$ ：前驱 $j$ 的合法范围。

2. 识别队列三大要素

只要你能把转移式子化成上面的形状，并且 $L(i)$ 和 $R(i)$ 随着 $i$ 增大也是单调不减的（即左右端点都在往右走），就可以上单调队列。

我们直接对着这个一般式，回答三个问题：

新候选进队条件是什么？ 随着 $i$ 的增加，把 $(R(i-1),R(i)]$ 中新解锁的下标依次放进队尾。对每个新下标 $j$ ，拿已经计算好的 $g(j)$ 和队尾比拼；第一轮则按顺序加入初始合法范围内的候选。 $R(i)$ 不变时，不用重复加入。
队尾劣解淘汰条件是什么？ 如果新候选 $j$ 比队尾更强，即 $g(q.back()) \le g(j)$ ，旧的队尾就可以无情抛弃。
队首老将过期条件是什么？ 当前合法的最老资格是 $L(i)$ 。如果队首存的下标 $q.front() < L(i)$ ，说明它太老了，已经被时代的边界淘汰，直接从队首踢掉。

这套方法直接穿透了题目的层层包装。无论是多重背包的单调队列优化，还是树上路径的滑动窗口，你只要把式子写出来，认准 $g(j)$ 、 $L(i)$ 和 $R(i)$ ，单调队列的三步走自然就水落石出了。

多重背包如何拆出这三个量，可以接着看《动态规划优化》第三节；学到那里时，再回来对照这一节。

十、总结与自检

把这四道题串起来看：

在 P1886 中，我们维护的是原数组数值 $a[i]$ ；
在 P1714 中，我们维护的是前缀和数值 $s[j]$ ；
在 P1725 中，我们维护的是 DP 的前驱分值 $f[j]$ ；
在 P2216 中，我们维护的是第一趟算出来的行极值 $mx[i][j]$ 和 $mn[i][j]$ 。

你看，窗口里装着的东西在变，但内核完全没变：当候选按顺序进入、按顺序过期时，如果新候选至少一样优，还能留得更久，旧候选就可以放心让位。

1. 课后自检题

在 P1714 切蛋糕中，如果把 q.push_back(0) 删掉，会漏掉哪类子段？这份代码的第一轮查询还会遇到什么问题？
在 P1725 琪露诺中，为什么新候选是 $i-l$ 而不是 $i$ ？在本讲的实现中，队空意味着什么，为什么此时不能访问 q.front()、继续转移？为什么要避免对表示不可达的 -INF 直接加分？
在 P2216 中，第二趟扫描计算出的每个窗口最值，究竟对应着原图上哪一个具体的正方形区域？