给一个数列，在所有它的子数列中取最小值相加，求问加和mod 1000000007
想了半天也没想出O(n)的解法，于是借鉴了Discussion：https://leetcode.com/problems/sum-of-subarray-minimums/discuss/2846390/PythonC%2B%2B-two-O(N)-approaches-using-monostack-(explained)
思路一：遍历数列，用stk保存上一个比当前值小的数字下标（即维护一个不降的单调栈），ans为从第一个数到当前数字的所有子数列中包含当前数字的子数列的最小值加和
1.遇到当前数字比栈顶小的时候不断pop栈顶，pop的次数加一即为当前数字截至目前作为子数列最小值的次数
2.遇到当前数字比栈顶大的时候，当前数字截至目前作为子数列最小值的次数为1
Both 1，2的情况需要叠加更新后栈顶对应的ans值，因为以栈顶元素作为最小值的子数列加入当前值，依然是栈顶元素最小
1 #907
2 #Runtime: 1099 ms
3 #Memory Usage: 16.7 MB
4
5 class Solution(object):
6 def sumSubarrayMins(self, arr):
7 """
8 :type arr: List[int]
9 :rtype: int
10 """
11 stk = []
12 ans = [0] * len(arr)
13 for i in range(len(arr)):
14 while stk and arr[stk[-1]] > arr[i]:
15 stk.pop()
16 if stk:
17 j = stk[-1]
18 else:
19 j = -1
20
21 ans[i] = ans[j] + (i - j) * arr[i]
22 stk.append(i)
23 return sum(ans) % 1000000007
思路二：遍历数列，用s保存上一个比当前值小的数字下标（即维护一个不降的单调栈），res保存总的加和
先在数列末尾加一个0，保证比数列里所有值都小
1.遇到当前数字比栈顶大的时候，将当前下标压入栈
2.遇到当前数字比栈顶小的时候不断pop栈顶每pop一次，需要累加的值为栈顶和次栈顶下标差*当前下表和栈顶的下标差*栈顶下标对应的数字
1 #907
2 #Runtime: 371 ms
3 #Memory Usage: 17.1 MB
4
5 class Solution(object):
6 def sumSubarrayMins(self, arr):
7 """
8 :type arr: List[int]
9 :rtype: int
10 """
11 s, res = [-1], 0
12 arr.append(0)
13 for i in range(len(arr)):
14 while arr[s[-1]] > arr[i]:
15 j, k = s.pop(), s[-1]
16 res += (j - k) * (i - j) * arr[j]
17 s.append(i)
18 return res % 1000000007