用 Python 编写程序，从列表中找出每个子列表的最小值之和

pythonserver side programmingprogramming更新于 2026/1/19 23:08:17

假设我们有一个名为 nums 的数字列表。我们必须找出 nums 中每个子列表 x 的最小值之和。如果答案太大，则将结果取 10^9 + 7 的模。

因此，如果输入为 nums = [5, 10, 20, 10, 0]，则输出将为 90，因为子列表为 [[5], [10], [20], [10], [0], [5,10], [10,20], [20,10], [10,0], [5,10,20], [10,20,10], [20,10,0], [5,10,20,10], [10,20,10,0], [5,10,20,10,0]]，其最小值为 [5, 10, 20, 10, 0, 5, 10, 10, 0, 5, 10, 0, 5, 0, 0]，所以总和是 90。

为了解决这个问题，我们将遵循以下步骤 −

ans := 0
s := 一个新列表
temp_sum := 0
对于 nums 中的每个索引和值，执行
- 当 s 和值 <= s 中最后一个列表索引 1 处的元素时，执行
  - temp_sum := temp_sum - s 中最后一个列表索引 2 处的元素
  - 从 s 中删除最后一个元素
- 如果 s 为空，则
  - 在 s 中插入一个包含三个元素 [index, value, (index + 1)*value] 的列表s
- 否则，
  - 插入一个包含三个元素的列表 [index, value, (index - s 最后一个列表的第一个元素)*value]
- temp_sum := temp_sum + s 中最后一个列表索引 2 处的元素
- ans := ans + temp_sum
返回 ans mod (10^9 + 7)

示例

让我们看看下面的实现以便更好地理解 −

def solve(nums):
   ans = 0
   s = []
   temp_sum = 0
   for index, value in enumerate(nums):
      while s and value <= s[-1][1]:
         temp_sum -= s[-1][2]
         s.pop()
      if not s:
         s.append([index, value, (index + 1) * value])
      else:
         s.append([index, value, (index - s[-1][0]) * value])
      temp_sum += s[-1][2]
      ans += temp_sum
   return ans % (10**9 + 7)

nums = [5, 10, 20, 10, 0]
print(solve(nums))