給一個數列，在所有它的子數列中取最小值相加，求問加和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