题目描述：

给定一个数组A，视B为A的子序列，找到所有子序列中最小数字的和，并相加。

若数字特别大，则将该数对10^9+7取模

Example 1:

input: [3,1,2,4]

output: 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 。

官方文章网址：https://leetcode.com/articles/sum-of-subarray-minimums/

手段2：单调栈

直觉：

For a specific j, let's try to count the minimum of each subarray [i, j]. The intuition is that as we increment j++, these minimums may be related to each other. Indeed, min(A[i:j+1]) = min(A[i:j], A[j+1]).

对于特定的j，让我们去计算每个子数组[i,j]的最小值。直觉就是我们让j不断地递增，这些最小值可能互相有关，实际上在数组中，i到j+1的最小值实际上就是i到j的最小值和j+1比较，而这个步骤。（正是这个表达式，产生了使用单调栈的思想）

Playing with some array like A = [1,7,5,2,4,3,9], with j = 6 the minimum of each subarray [i, j] is B = [1,2,2,2,3,3,9]. We can see that there are critical points i = 0, i = 3, i = 5, i = 6 where a minimum is reached for the first time when walking left from j.

让我们假定一个数组像 A = [1,7,5,2,4,3,9]，当j = 6时，从i开始最小的数分别是B = [1,2,2,3,3,9]，我们可以看到，当从j向左走时，存在临界点i=0，i=3，i=5，i=6，其中第一次达到最小值。

算法：

Let's try to maintain an RLE (run length encoding) of these critical points B. More specifically, for the above (A, j), we will maintain stack = [(val=1, count=1), (val=2, count=3), (val=3, count=2), (val=9, count=1)], that represents a run length encoding of the subarray minimums B = [1,2,2,2,3,3,9]. For each j, we want sum(B).

让我们尝试处理这些临界点B的RLE（行程编码），更具体的来说，对于上面的(A,j)，我们实施一个栈，这个栈在上面的例子中，会变成这样： [(val=1, count=1), (val=2, count=3), (val=3, count=2), (val=9, count=1)]。

As we increment j, we will have to update this stack to include the newest element (val=x, count=1). We need to pop off all values >= x before, as the minimum of the associated subarray [i, j] will now be A[j] instead of what it was before.

当我们递增j时，我们将不得不更新这个栈及最新元素，我们需要把所有比A[j]大或等于的值弹出栈，让这个栈控制在最小值得控制下，同时每弹出一个，count就增加，直到新元素入栈，count重置为1。

At the end, the answer is the dot product of this stack: ∑e ∈ stacke.val∗e.counte ∈ stack∑​e.val∗e.count, which we also maintain on the side as the variable dot.

最后，答案就是栈的点积之和。

C++代码：

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
using namespace std;
int mod = pow(10,9)+7;
int sumSubarrayMins(vector<int>& A) {int MOD = 1000000007;stack<pair<int,int>> stack;int ans = 0, dot = 0;for (int j = 0; j < A.size(); ++j) {// Add all answers for subarrays [i, j], i <= jint count = 1;if(!stack.empty())while (!stack.empty() && stack.top().first >= A[j]) {pair<int,int> node = stack.top();stack.pop();count += node.second;dot -= node.first * node.second;}stack.push(make_pair(A[j], count));dot += A[j] * count;ans += dot;ans %= MOD;}return ans;
}
int main()
{vector<int>v;v.push_back(3);v.push_back(1);v.push_back(2);v.push_back(4);cout<<sumSubarrayMins(v)<<endl;}