如何将寻找固定长度最大最小子数组的解法改写为分治实现

你要解决的是固定长度滑动窗口的最大最小值问题：给定数组_in和固定长度l，找出所有长度为l的子数组中，子数组的最小值最大的那个子数组的起始下标和对应子数组。

分治核心逻辑是「拆分-求解-合并」，针对该问题的具体步骤如下：

• 终止条件：当当前处理的子数组长度刚好等于l时，直接返回该子数组的起始下标和子数组的最小值作为当前区间的最优解
• 拆分：将当前数组从中间位置拆分为左、右两个子区间
• 递归求解：分别递归计算左子区间、右子区间的最优解
• 合并：额外计算横跨左右两个子区间的所有合法长度为l的子数组的最优解，再将左、右、跨区间三个最优解对比，取最小值最大的那一个作为整个区间的最优解返回

def divide_conquer(_in, l, start, end):
    # 当前区间的长度
    n = end - start
    # 终止条件：区间长度刚好等于l，直接返回结果
    if n == l:
        return start, min(_in[start:end])
    
    # 拆分中点
    mid = (start + end) // 2
    
    # 递归求解左右子区间的最优解
    left_best_idx, left_best_min = divide_conquer(_in, l, start, mid)
    right_best_idx, right_best_min = divide_conquer(_in, l, mid, end)
    
    # 求解跨左右区间的最优解：合法子数组起点范围是 [max(start, mid - l + 1), min(mid, end - l)]
    cross_best_min = -float('inf')
    cross_best_idx = -1
    cross_start_min = max(start, mid - l + 1)
    cross_start_max = min(mid, end - l)
    for i in range(cross_start_min, cross_start_max + 1):
        current_min = min(_in[i:i+l])
        if current_min > cross_best_min:
            cross_best_min = current_min
            cross_best_idx = i
    
    # 三者对比取最优
    candidates = [
        (left_best_min, left_best_idx),
        (right_best_min, right_best_idx),
        (cross_best_min, cross_best_idx)
    ]
    best_min, best_idx = max(candidates)
    return best_idx, best_min

def main(_in, l):
    n = len(_in)
    if n < l:
        return -1, []
    best_idx, _ = divide_conquer(_in, l, 0, n)
    return best_idx, _in[best_idx:best_idx+l]

输入测试用例：

arr = [5, 1, -1, 2, 5, -4, 3, 9, 8, -2, 0, 6]
l = 3
print(main(arr, l))

输出结果为(6, [3, 9, 8])，和预期结果一致。

你原本的暴力实现时间复杂度为O(n*l)，分治版本的时间复杂度优化为O(n log n)，适合处理数组长度大、窗口长度l也较大的场景。

内容的提问来源于stack exchange，提问作者Ellis Thompson