题解

思路

使用双指针维护以当前右端点结尾的最长合法窗口。右端点增加后，若极差超过 $k$，左端点只会向右移动，不会回退。

做法

当序列单调不下降时，窗口极差就是 $a_r-a_l$，普通双指针即可。若 $k=0$，答案等于最长连续相等段。对于 $n\le2000$，可以枚举左端点并逐步更新最大值、最小值，复杂度为 $O(n^2)$。

满分算法维护两个下标双端队列：

• 最小值队列中的值单调递增；
• 最大值队列中的值单调递减。

加入 $a_r$ 时，从队尾删除不可能再成为极值的元素，然后把 $r$ 入队。当两队队首之差大于 $k$ 时，逐个右移左端点；若离开的下标恰为队首，就将其弹出。此时两个队首始终分别是当前窗口的最小值与最大值。

正确性

固定右端点 $r$。随着左端点右移，窗口最大值不会增大、最小值不会减小，因此极差单调不增；存在唯一最靠左的合法位置。算法只在窗口非法时移动左端点，停止时恰好到达该位置，所以得到以 $r$ 结尾的最长合法子段。枚举所有 $r$ 并取最大值即得全局最优。

被单调队列从队尾删除的元素，右侧已有一个更优且更晚离开的候选，因此它不可能再成为未来窗口极值；队首过期时及时删除，所以维护的极值准确。

复杂度

每个下标在两个队列中各入队、出队至多一次，时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。