列表推导式问题：求数组所有子数组最小值之和的代码排查

原代码核心错误 #

1. 变量未定义错误：列表推导式中先写了for i in range(j-1, len(arr))，但此时j还未被初始化，运行时会直接抛出NameError: name 'j' is not defined。
2. 子数组生成逻辑错误：就算调整循环顺序，原有的i的范围设置也无法覆盖所有合法子数组。正确的子数组应该是从索引i开始到j结束（左闭右开），其中i的取值范围是0 <= i < len(arr)，j的取值范围是i+1 <= j <= len(arr)。

修复后的代码 #

class Solution(object):
    def sumSubarrayMins(self, arr):
        total = 0
        n = len(arr)
        # 正确生成所有子数组并累加最小值
        for i in range(n):
            for j in range(i + 1, n + 1):
                total += min(arr[i:j])
        return total

sol = Solution()
print(sol.sumSubarrayMins([3,1,2,4]))  # 输出应为 17

进一步优化（降低空间复杂度） #

原代码中存储所有子数组会占用O(n²)的空间，我们可以直接在循环中维护当前子数组的最小值，避免生成子数组切片，进一步优化性能：

class Solution(object):
    def sumSubarrayMins(self, arr):
        total = 0
        n = len(arr)
        for i in range(n):
            current_min = arr[i]
            total += current_min
            for j in range(i + 1, n):
                current_min = min(current_min, arr[j])
                total += current_min
        return total

sol = Solution()
print(sol.sumSubarrayMins([3,1,2,4]))  # 输出 17

说明 #

• 第一个修复版本先修正了循环顺序和索引范围，确保能生成所有合法子数组，再累加每个子数组的最小值。
• 优化版本通过维护当前子数组的最小值，避免了每次生成子数组切片的开销，空间复杂度从O(n²)降到O(1)，时间复杂度仍为O(n²)。如果需要更优的时间复杂度（O(n)），可以使用单调栈的方法，但上述版本已经解决了你当前代码的运行问题。

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