绝对差不超过限制的最长连续子数组

记住「maxq 递减管最大、minq 递增管最小;右扩弹尾入队、超限左缩弹首、记最长」,下面每一格都在套它。

这一行是数组。maxq、minq 都从空开始,左指针在 0;右指针一格格往右扩,我们盯着两个队列、窗口 max−min,还有最长长度怎么变。

右指针扩到第 0 位,值 10。入队前先维护单调:maxq 尾部都不比 10 小,不弹;minq 尾部都不比 10 大,不弹。然后把下标 0 入两个队。

读队首:窗口最大是 10(下标 0)、最小是 10(下标 0),差 0 不超过 limit 5,这段合法。长度 0−0+1=1,比之前长,最长刷新成 1。

右边再纳入第 1 位,值 1。入队前先维护单调:maxq 尾部都不比 1 小,不弹;minq 尾部比 1 大的也当不了最小,弹掉。然后把下标 1 入两个队。

读队首:最大 10、最小 1,差 9 已经超过 limit 5(标红)。这段不合法,要把左指针往右收,直到差重新合法。

左指针从 0 右移到 1:谁的队首下标正好滑出了窗口,就把它从队首弹掉。现在 max−min=0 ≤ 5,窗口 [1, 1] 合法,长度 1,最长仍是 1。

右指针推进到第 2 位,值 2。入队前先维护单调:maxq 尾部那些比 2 小的值再也当不了最大,弹掉;minq 尾部都不比 2 大,不弹。然后把下标 2 入两个队。

读队首:窗口最大是 2(下标 2)、最小是 1(下标 1),差 1 不超过 limit 5,这段合法。长度 2−1+1=2,比之前长,最长刷新成 2。

窗口右扩到第 3 位,值 4。入队前先维护单调:maxq 尾部那些比 4 小的值再也当不了最大,弹掉;minq 尾部都不比 4 大,不弹。然后把下标 3 入两个队。

读队首:窗口最大是 4(下标 3)、最小是 1(下标 1),差 3 不超过 limit 5,这段合法。长度 3−1+1=3,比之前长,最长刷新成 3。

右端来到第 4 位,值 7。入队前先维护单调:maxq 尾部那些比 7 小的值再也当不了最大,弹掉;minq 尾部都不比 7 大,不弹。然后把下标 4 入两个队。

读队首:最大 7、最小 1,差 6 已经超过 limit 5(标红)。这段不合法,要把左指针往右收,直到差重新合法。

左指针从 1 右移到 2:谁的队首下标正好滑出了窗口,就把它从队首弹掉。现在 max−min=5 ≤ 5,窗口 [2, 4] 合法,长度 3,最长仍是 3。

继续右扩到第 5 位,值 2。入队前先维护单调:maxq 尾部都不比 2 小,不弹;minq 尾部比 2 大的也当不了最小,弹掉。然后把下标 5 入两个队。

读队首:窗口最大是 7(下标 4)、最小是 2(下标 2),差 5 不超过 limit 5,这段合法。长度 5−2+1=4,比之前长,最长刷新成 4。

扫完全程,最长的合法窗口长度是 4。回头看:每个下标进出两个单调队列各一次、左右指针各只前进一遍,所以是 O(n)。

边界:单元素恒为 1;limit=0 要求窗口内全相等;全相等时整段都合法。

面试常考:两个单调队列各管 max/min,以及对比有序集合 O(n log n) 解法。