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

更新於: 2021年10月18日

218 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告