LeetCode子数组最小值之和：归并排序解法错误排查

我是Python新手，尝试用归并排序思路解决LeetCode的子数组最小值之和问题。该问题要求计算数组中所有连续子数组的最小值之和，例如数组[1,2,3]的结果为10（计算逻辑：所有子数组的最小值相加：[1]→1、[1,2]→1、[1,2,3]→1、[2]→2、[2,3]→2、[3]→3，总和1+1+1+2+2+3=10）。我编写的代码在处理长数组时，预期输出为508796209，但实际输出为2508796223，找不到问题所在。查找归并排序的解法时，大多是单调栈实现，因此求助。

我的代码如下：

class Solution:
    def __init__(self):
        self.sum_of_nums = 0
    def sumSubarrayMins(self, arr: list[int]) -> int:
        if len(arr) > 0:
            smallest = arr.index(min(arr))
            left = arr[:smallest]
            right = arr[smallest+1:]
            self.sumSubarrayMins(left)
            self.sumSubarrayMins(right)
            self.sum_of_nums += (len(left)+1)*(len(right)+1)*arr[smallest]
        return self.sum_of_nums

给定长数组：[29959,29867,29822,...,29871]

问题分析 #

你的代码存在两个关键问题：

• 未按题目要求取模：LeetCode该问题明确要求结果对10^9+7（即1000000007）取模。你的实际输出2508796223是未取模的原始总和，计算其模1000000007的结果：2508796223 - 2*1000000007 = 508796209，正好与预期输出一致。
• 重复元素的潜在逻辑漏洞：当数组中存在多个相同最小值时，arr.index(min(arr))只会返回第一个最小值的索引。虽然部分案例结果正确，但极端场景（如大量分散的相同最小值）可能导致递归时重复计算或漏算子数组。

修正后的代码 #

优化后的代码添加取模操作，并限定最小值索引的搜索范围，避免跨区间错误：

class Solution:
    MOD = 10**9 + 7
    def sumSubarrayMins(self, arr: list[int]) -> int:
        def merge_sort(l, r):
            if l > r:
                return 0
            if l == r:
                return arr[l] % self.MOD
            
            # 在当前区间[l, r]内查找最小值的索引
            min_val = min(arr[l:r+1])
            mid = arr.index(min_val, l, r+1)
            
            # 计算当前最小值贡献的总和
            left_count = mid - l + 1
            right_count = r - mid + 1
            contribution = (left_count * right_count) % self.MOD
            contribution = (contribution * min_val) % self.MOD
            
            # 递归处理左右子区间
            left_sum = merge_sort(l, mid-1)
            right_sum = merge_sort(mid+1, r)
            
            return (left_sum + right_sum + contribution) % self.MOD
        
        return merge_sort(0, len(arr)-1)

修正说明 #

1. 用局部递归函数替代类成员变量，避免全局状态带来的副作用。
2. 每一步计算都对结果取模，确保数值符合题目要求的范围。
3. 限定arr.index的搜索范围为当前递归区间[l, r]，避免跨区间查找错误的最小值索引。

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