主題
題目連結：
題目意譯：
給定一整數陣列 arr，請算出 min(b) 之總和，其中 b 涵蓋了 arr 的每一個（連續）子陣列。由於答案可能很大，將其模 10 ^ 9 + 7 後再回傳。
限制：
1 ≦ arr.length ≦ 3 × 10 ^ 4
1 ≦ arr[i] ≦ 3 × 10 ^ 4
範例測資：
範例 1：
輸入： arr = [3,1,2,4]
輸出： 17
解釋：
子陣列為 [3] 、 [1] 、 [2] 、 [4] 、 [3,1] 、 [1,2] 、 [2,4] 、 [3,1,2] 、 [1,2,4] 、 [3,1,2,4]。
最小值為 3 、 1 、 2 、 4 、 1 、 1 、 2 、 1 、 1 、 1
總和為 17。
範例 2：
輸入： arr = [11,81,94,43,3]
輸出： 444
解題思維：
假設現在我們想要知道某個元素 nums[i] 在多少個子陣列是作為最小值存在：
令 L(i) 為從 nums[i] 開始往左可以延伸到何處且當中路徑上的數字都不小於 nums[i]，也就是說 nums[L(i)]（含）～ nums[i]（含）中的所有數字都不小於 nums[i] 本身；同樣地，我們令 R(i) 代表著 nums[i] 最遠可以往右延伸到何處。
此時我們可以看到，根據定義 nums[L(i)]（含）～ nums[R(i)]（含）的這段子陣列取出任何一個有包含 nums[i] 的子陣列，nums[i] 都會是作為最小值存在。並且，nums[i] 只會在這些子陣列中是最小值。
因此，我們可以看到這些子陣列的數量即為 (i - L(i) + 1) × (R(i) - i + 1) 個。
因此為了求出所求，我們需要知道每一個元素 nums[i] 各自的 L(i) 和 R(i)。而這邊可以套用類似於這題的想法來解決，也就是使用一個堆疊（Stack）並維護其遞增性。
可以看到每當我們看到一個新元素 nums[i]，而它小於堆疊頂端的元素 nums[t]，這也就代表著 nums[i] 決定了 nums[t] 的 R(t) 之值。而堆疊頂端下面一個元素（如果有的話；也就是把現有的頂端元素移除之後的新頂端元素）nums[t']，則因為堆疊遞增性而決定了 nums[t] 的 L(t)。
因此此時我們便可以算出頂端元素 nums[t] 的 L(t)（如果下一個元素 nums[t'] 不存在，則代表著它可以一直延伸到 nums[0]）和 R(t)，並算出 nums[t] 在多少子陣列中是作為最小值存在。算完之後 nums[t] 便可以從堆疊頂端移除。
而 nums[t'] 也有可能小於 nums[i]，因此我們可以重複以上步驟直到堆疊為空或是條件不滿足為止。最後把 nums[i] 放到堆疊頂端便可以維持其遞增性。
最後 nums 中的數字都掃完之後，堆疊有可能不為空，此時代表著這裡面所有元素的 R(i) 都是 nums 的結尾（因為代表沒有其他人小過它們了）。此時我們便可以決定這些剩下的數字之 L(i) 和 R(i)。最後將所有求出的子陣列數量加總即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
