<div><p>Given an array of integers arr, find the sum of <code>min(b)</code>, where <code>b</code> ranges over every (contiguous) subarray of <code>arr</code>. Since the answer may be large, return the answer <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>
<p> </p> <p><strong>Example 1:</strong></p>
<pre><strong>Input:</strong> arr = [3,1,2,4] <strong>Output:</strong> 17 <strong>Explanation:</strong> Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17. </pre>
<p><strong>Example 2:</strong></p>
<pre><strong>Input:</strong> arr = [11,81,94,43,3] <strong>Output:</strong> 444 </pre>
<p> </p> <p><strong>Constraints:</strong></p>
<ul> <li><code>1 <= arr.length <= 3 * 10<sup>4</sup></code></li> <li><code>1 <= arr[i] <= 3 * 10<sup>4</sup></code></li> </ul> </div>
题目大意：
求所有子数组的最小值的和
算法思路：
求区间最值用Stack，因为是最小值，所以用递增栈
一开始考虑用类似DP，因为若知道[3, 2, 6]栈为[2, 6], 8入栈，8与每一个栈内元素计算最小值，优化是用栈内的累计和，如2和6对应的累计和而不用每个元素计算。
参考了网上算法，栈内每个元素向左向右区间内（包括自己）均是最小值，所以出栈时候进行计算即可。
如[3, 2, 8, 7, 6, 9, 10, 4]栈是[2, 6, 9, 10]对应的下标，现在4入栈，9和10出栈后，6准备出栈。
prev_idx为6的下标4， i是7，6是[8, 7, 6], [7, 6], [6]三个区间的最小值prev_idx - stack[-1] = 3个区间，
而这些区间的最小值的和还要再乘以后面的大于它的数，如[7, 6]这个区间可以和这些区间合并[7, 6], [7, 6, 9], [7, 6, 9, 10], 所以(i - prev_idx) = 3
这就是arr[prev_idx] * (prev_idx - stack[-1]) * (i - prev_idx)的精髓
注意事项：
- 头尾加入最小值，加入头部因为公式需要栈内的前元素，这样可以处理只有一个元素出栈的情况。尾部加入最小值因为确保所有元素都出栈。
Python代码：
1
2
3
4
5
6
7
8
9
10
11def sumSubarrayMins(self, arr: List[int]) -> int:
arr.insert(0, -sys.maxsize)
arr.append(-sys.maxsize)
stack, res = [], 0
for i in range(len(arr)):
while stack and arr[i] < arr[stack[-1]]:
prev_idx = stack.pop()
res += arr[prev_idx] * (prev_idx - stack[-1]) * (i - prev_idx)
res = res % (pow(10, 9) + 7)
stack.append(i)
return res
算法分析：
时间复杂度为O(n)，空间复杂度O(n)
