Python程序：查找列表中每个子列表的最小值的总和

假设我们有一个名为nums的数字列表。我们需要找到nums中每个子列表x的最小值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中插入一个包含三个元素的列表[索引，值，(索引 + 1)*值]
  • 否则，
    • 插入一个包含三个元素的列表[索引，值，(索引 - s中最后一个列表的第一个元素)*值]
  • temp_sum := temp_sum + s中最后一个列表的索引2处的元素
  • ans := ans + temp_sum
• 返回ans模 (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))

输入

[5, 10, 20, 10, 0]

输出

90

Arnab Chakraborty

更新于: 2021年10月18日

218 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习