這題如果用動態(tài)規(guī)劃方法求解智润，復(fù)雜度苟跪，在給定的數(shù)據(jù)規(guī)模下挪蹭，肯定超時(shí)已添。
轉(zhuǎn)變思路忌穿，計(jì)算數(shù)組中的第個(gè)元素
可以作為多少個(gè)子數(shù)組的最小值笙隙，這個(gè)數(shù)量記為
，那么arr[i]提供的子數(shù)組最小值和就是
隔心。然后遍歷一遍arr白群，就能求出本題的答案了。
那么問題就變成了怎么計(jì)算了硬霍，加入
左邊有3個(gè)數(shù)小于
帜慢，
右邊有1個(gè)數(shù)小于
，那么這種情況下的
唯卖×涣幔可以看出，只要找到
左右兩邊第一個(gè)小于
的數(shù)的位置拜轨。
這個(gè)問題如果用遍歷試探去找的話抽减，復(fù)雜度還是還是會超時(shí)，這里介紹單調(diào)棧方法撩轰，可以棧
的復(fù)雜度內(nèi)計(jì)算出左邊最近的小于
的數(shù)（的位置）胯甩。
- 對于當(dāng)前遍歷的元素
，觀察棧頂?shù)脑乜吧绻麠ｍ數(shù)脑卮笥甑扔诋?dāng)前元素偎箫，就把棧頂元素出棧，重復(fù)這個(gè)過程皆串，直到棧為空或者棧頂元素小于當(dāng)前元素淹办，這樣我們就找到了
- 然后再把
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
總結(jié)：
單調(diào)棧的本質(zhì)：快速找到左邊谤牡、右邊最近的大于或小于自身的值（或位置）副硅。
如果要找最近小于自身的數(shù)（位置），使用單調(diào)遞增棧翅萤，棧頂小于自身就是結(jié)果恐疲。
如果要找最近大于自身的數(shù)（位置），使用單肩遞減棧套么，棧頂大于自身就是結(jié)果培己。
單調(diào)隊(duì)列的本質(zhì)：在運(yùn)行的過程中，能夠快速找到前K個(gè)或后K個(gè)中的最值胚泌。
能夠維護(hù)一個(gè)區(qū)間的最值省咨，這個(gè)區(qū)間的兩個(gè)下標(biāo)在運(yùn)行過程中，都是往右跑玷室，不會往左跑零蓉。
