給一個數(shù)列，在所有它的子數(shù)列中取最小值相加，求問加和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)
思路一：遍歷數(shù)列，用stk保存上一個比當(dāng)前值小的數(shù)字下標(biāo)（即維護一個不降的單調(diào)棧），ans為從第一個數(shù)到當(dāng)前數(shù)字的所有子數(shù)列中包含當(dāng)前數(shù)字的子數(shù)列的最小值加和
1.遇到當(dāng)前數(shù)字比棧頂小的時候不斷pop棧頂，pop的次數(shù)加一即為當(dāng)前數(shù)字截至目前作為子數(shù)列最小值的次數(shù)
2.遇到當(dāng)前數(shù)字比棧頂大的時候，當(dāng)前數(shù)字截至目前作為子數(shù)列最小值的次數(shù)為1
Both 1，2的情況需要疊加更新后棧頂對應(yīng)的ans值，因為以棧頂元素作為最小值的子數(shù)列加入當(dāng)前值，依然是棧頂元素最小
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
思路二：遍歷數(shù)列，用s保存上一個比當(dāng)前值小的數(shù)字下標(biāo)（即維護一個不降的單調(diào)棧），res保存總的加和
先在數(shù)列末尾加一個0，保證比數(shù)列里所有值都小
1.遇到當(dāng)前數(shù)字比棧頂大的時候，將當(dāng)前下標(biāo)壓入棧
2.遇到當(dāng)前數(shù)字比棧頂小的時候不斷pop棧頂每pop一次，需要累加的值為棧頂和次棧頂下標(biāo)差*當(dāng)前下表和棧頂?shù)南聵?biāo)差*棧頂下標(biāo)對應(yīng)的數(shù)字
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