链接：子数组的最小值之和
这题如果用动态规划方法求解，复杂度，在给定的数据规模下，肯定超时。
转变思路，计算数组中的第个元素
可以作为多少个子数组的最小值，这个数量记为
，那么arr[i]提供的子数组最小值和就是
。然后遍历一遍arr，就能求出本题的答案了。
那么问题就变成了怎么计算了，加入
左边有3个数小于
，
右边有1个数小于
，那么这种情况下的
。可以看出，只要找到
左右两边第一个小于
的数的位置。
这个问题如果用遍历试探去找的话，复杂度还是还是会超时，这里介绍单调栈方法，可以栈
的复杂度内计算出左边最近的小于
的数（的位置）。
- 对于当前遍历的元素
，观察栈顶的元素，如果栈顶的元素大雨等于当前元素，就把栈顶元素出栈，重复这个过程，直到栈为空或者栈顶元素小于当前元素，这样我们就找到了
- 然后再把
class Solution:
def sumSubarrayMins(self, arr: List[int]) -> int:
n = len(arr)
base = 10**9+7
res = 0
stack = []
prev = [0]*n
next = [0]*n
for i in range(n):
while stack and arr[i] < stack[-1][0]:
stack.pop()
prev[i] = stack[-1][1] if stack else -1
stack.append([arr[i], i])
stack = []
for i in reversed(range(n)):
while stack and arr[i] <= stack[-1][0]:
stack.pop()
next[i] = stack[-1][1] if stack else n
stack.append([arr[i], i])
# print(prev)
# print(next)
for i in range(n):
res = (res + arr[i] * (i-prev[i])*(next[i]-i)) % base
return res
总结：
单调栈的本质：快速找到左边、右边最近的大于或小于自身的值（或位置）。
如果要找最近小于自身的数（位置），使用单调递增栈，栈顶小于自身就是结果。
如果要找最近大于自身的数（位置），使用单肩递减栈，栈顶大于自身就是结果。
单调队列的本质：在运行的过程中，能够快速找到前K个或后K个中的最值。
能够维护一个区间的最值，这个区间的两个下标在运行过程中，都是往右跑，不会往左跑。
