基于分治法求解实数数组最小乘积前缀对应k值的实现问题

核心逻辑 #

分治的核心是将原问题递归拆分为多个规模相近的子问题，分别求解后合并结果，而非每次仅缩小1个问题规模（你之前的实现属于减治，本质是递归形式的线性遍历）。
对于本问题，我们将数组从中间拆分为左右两个子数组，最小前缀的k只会出现在两种场景：

• k落在左半子数组范围内：此时解就是左半子问题的最优解
• k落在右半子数组范围内：此时前缀乘积 = 左半子数组的总乘积 * 右半子数组从起点到k的前缀乘积
  由于数组元素包含实数（存在负数），乘积的大小关系会随乘数的正负翻转，因此每个子问题需要返回4个结果：
• 子数组范围内最小前缀乘积对应的下标min_k
• 子数组范围内最小前缀乘积的值min_val
• 子数组范围内最大前缀乘积的值max_val
• 子数组所有元素的总乘积total

合并规则 #

假设我们已经得到左半子数组（范围[l, mid]）的四个结果，以及右半子数组（范围[mid+1, r]）的四个结果，合并步骤如下：

1. 计算当前数组的总乘积：current_total = left.total * right.total
2. 计算右半前缀映射到整个数组的最小、最大乘积：
   • 若左半总乘积为正：右半的最小前缀乘积乘左半总乘积仍为最小，最大前缀乘积乘后仍为最大
   • 若左半总乘积为负：右半的最大前缀乘积乘左半总乘积会变为最小，最小前缀乘积乘后会变为最大
   • 若左半总乘积为0：右半所有前缀映射后的乘积均为0
3. 对比左半的最小前缀乘积和右半映射后的最小前缀乘积，取更小的那个对应的下标作为当前数组的min_k，对应值为current_min_val
4. 同理对比左半的最大前缀乘积和右半映射后的最大前缀乘积，得到current_max_val

伪代码实现 #

# 输入：数组arr，当前处理范围[l, r]（下标从1开始）
# 返回：(min_k, min_val, max_val, total)
function min_prefix_divide(arr, l, r)
    # 递归终止条件：子数组只有一个元素
    if l == r
        return (l, arr[l], arr[l], arr[l])
    end
    
    mid = (l + r) // 2
    # 递归求解左右子问题
    left_min_k, left_min_val, left_max_val, left_total = min_prefix_divide(arr, l, mid)
    right_min_k, right_min_val, right_max_val, right_total = min_prefix_divide(arr, mid+1, r)
    
    # 计算右半映射后的最小、最大乘积及对应下标
    if left_total > 0
        cross_min_val = left_total * right_min_val
        cross_min_k = right_min_k
        cross_max_val = left_total * right_max_val
        cross_max_k = right_max_k
    elif left_total < 0
        cross_min_val = left_total * right_max_val
        cross_min_k = right_max_k
        cross_max_val = left_total * right_min_val
        cross_max_k = right_min_k
    else
        cross_min_val = 0
        cross_min_k = mid + 1
        cross_max_val = 0
        cross_max_k = mid + 1
    end
    
    # 合并得到当前数组的结果
    current_total = left_total * right_total
    if cross_min_val < left_min_val
        current_min_k = cross_min_k
        current_min_val = cross_min_val
    else
        current_min_k = left_min_k
        current_min_val = left_min_val
    end
    
    if cross_max_val > left_max_val
        current_max_val = cross_max_val
    else
        current_max_val = left_max_val
    end
    
    return (current_min_k, current_min_val, current_max_val, current_total)
end

# 主调用入口
function get_min_prefix_k(arr, n)
    min_k, _, _, _ = min_prefix_divide(arr, 1, n)
    return min_k
end

复杂度说明 #

• 时间复杂度：O(n)，递归深度为O(logn)，每个元素仅被处理一次，总操作数线性增长
• 空间复杂度：O(logn)，为递归栈的开销

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