題目如下

數(shù)據(jù)范圍

  觀察數(shù)據(jù)范圍理論上平方復雜度的算法計算次數(shù)逼近1e9還不至于超時，但是由于有mod 1e9導致超時。所以本題不能靠暴力枚舉來解決。
所以我們可以思考如何在枚舉上面減少計算次數(shù)：第一種枚舉法：最外層i控制子數(shù)組的左邊界，內(nèi)層則從左邊界開始遍歷到最后其中維持最小值。如此可以枚舉完所有的子數(shù)組，顯然超時。這種枚舉法不好在忽略了一個值可能是很多子數(shù)組的最小值。例如 在數(shù)組[3,1,2,4]中子數(shù)組[3,1,2] [1,2]最小值都是1所以不方便減少計算次數(shù)。第二種枚舉法：因為子數(shù)組長度最小可以為1所以每個數(shù)都可以至少是一個子數(shù)組的最小值，我們可以通過從一個數(shù)出發(fā)向左向右尋找第一個小于這個數(shù)的左右邊界。我們只需要算出在這個邊界能形成多少個包含i的子數(shù)組就可以得到以arr[i]為最小值的子數(shù)組的數(shù)量。（即從[l,i] [i,r]各自選1個值就行 排列組合的思想）顯然也超時，但是很好利用了特性。
所以我們來思考如何減少第二種枚舉法的復雜度：因為向左向右尋找的思路一樣所以這里就僅說明向左尋找的思路。顯然每次向左搜索第一個小于這個數(shù)的重復計算太多，我們可以想想幾種情況如果數(shù)組有(i,j都是下標且i < j)那么我們令i j對應(yīng)的第一個小于的坐標為i1 和 j1，當arr[i] > arr[j]時 有i1 >= j1(j >= j1) 我們記為1情況當arr[i] <= arr[j]時 有i1 <= j1 我們記為2情況
從兩個情況我們可以看出j可能會被i作為答案所以我們先存起來，如果j不是i答案那么i的答案i1必然在j1前所以尋找j1所排除的與i1并無關(guān)系甚至推廣來說只要當前處理的i下標大于j那么因為j排掉的答案并不是i的答案。換句話說我們處理完j以后只需要把j存起來以防萬一i的答案是j就行。所以我們可以考慮引入單調(diào)棧從左到右遍歷數(shù)組（按嚴格遞增的趨勢）對每個處理的i如果棧頂大于等于就出棧直到棧空或者棧頂小于arr[i]。如此便確定左邊界，當然我們采用左開右開的區(qū)間方便計算（使用-1作為哨兵）。右邊界同理只不過是從右往左遍歷這里不多贅述。那么這里還要注意處理重復區(qū)間：當我們允許左邊界包含重復數(shù)字時就不能讓右邊界包含了，假設(shè)數(shù)組存在多個重復值任選兩個兩個一樣的數(shù)，如果我們讓左右都可以包含重復值就會產(chǎn)生重復計算所以只能讓一邊可以包含重復值。

通過代碼

class Solution {
public:int sumSubarrayMins(vector<int>& arr) {int n = arr.size(),mod = (1e9 + 7),ans = 0;vector<int> l(n),r(n);stack<int> s;for (int i = 0; i < n; i++) {while(!s.empty() && arr[s.top()] > arr[i]){s.pop();}l[i] = (s.empty())?-1:s.top();s.push(i);}s = stack<int>();for (int i = n - 1; i >= 0; i--) {while(!s.empty() && arr[s.top()] >= arr[i]){s.pop();}r[i] = (s.empty())?n:s.top();s.push(i);}for(int i = 0;i < n;i++){ans = (ans + (long long)arr[i] * (i - l[i]) * (r[i] - i)) % mod;}return ans; }};