Meta 极差至少k的最短子数组：双单调队列

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 返回最短长度，不存在返回None；空数组没有非空解。k<=0且数组非空返回1。
• max−min>=k是可行条件，不是<=k。整数值可以为负，单调队列用下标支持准确过期。

解题路线

1. 维护递增队列low得到窗口最小、递减队列high得到最大；新元素淘汰队尾不再可能成为最值的旧候选。
2. 窗口满足极差>=k时立即记录长度，然后尝试移走左端以求更短。直到收缩后不满足才停止，等待右端扩张。
3. 对于每个right，收缩过程枚举其所有仍可行的左端直到边界，必然记录最短可行窗。每下标最多入出每队一次，总工作线性。

手动走一遍

[1,10,2]、k=8，长度2的[1,10]或[10,2]可行，结果2；[2,2,2]、k=1无解；k=0时单元素足够。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from collections import deque


def shortest_range_at_least(values, k):
    """Shortest nonempty subarray whose max-min >= k; return length or None."""
    if not values:
        return None
    if k <= 0:
        return 1
    low, high = deque(), deque()
    left = 0
    best = None
    for right, value in enumerate(values):
        while low and values[low[-1]] >= value:
            low.pop()
        while high and values[high[-1]] <= value:
            high.pop()
        low.append(right); high.append(right)
        while values[high[0]] - values[low[0]] >= k:
            size = right - left + 1
            best = size if best is None else min(best, size)
            if low[0] == left:
                low.popleft()
            if high[0] == left:
                high.popleft()
            left += 1
    return best

复杂度

O(n)时间，O(n)最坏辅助空间；保存结果只O(1)。有些窗口队列实际短，但不能声称严格O(k)，k是数值极差阈值。

易错点与追问

容易失分的边界

• 把条件写为while极差>k收缩是在做最长<=k题，会求出完全不同答案。
• 队列保存值而非下标时重复值过期易错；下标让离开窗口的候选可直接判断。

继续深挖

• 要求极差<=k的最长窗时，收缩不合法窗口直到可行，再更新最长；需要重新解释不变量。
• 若仅问存在长度至多L的可行片段，可用固定上限窗口最值；最短长度仍由本算法更直接。