lintcode-1734 · 子数组的最小值之和

描述

给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。

由于答案可能很大，因此模 10^9 + 7以后返回答案。

**

• 1 \leq A \leq 300001≤A≤30000
• 1 \leq A[i] \leq 300001≤A[i]≤30000

样例

样例 1:

输入：[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:

输入：[95,58,46,67,100]
输出：859
解释：
子数组为 [95], [58], [46], [67], [100], [98,58], [58,46], [46,67], [67,100], [95,58,67],[46,67,100],[95,58,46,67],[58,46,67,100],[95,58,46,67,100]。 
最小值为 95, 58, 46, 67, 100, 58, 46, 46, 67, 46, 46, 46, 46, 46, 46，和为 859。

题解

刚看到题目的时候，第一想法就是跑两个循环，找到所有的子数组，然后找到最小值。累计求和。不过这种方法的复杂度是0(n^2)。
首先我们观察一下题目中给出的结果：

对于[3,1,2,4]：
最小值是1：[1],[3,1],[3,1,2],[3,1,2,4],[1,2],[1,2,4]
最小值是2：[2], [2,4]

其实对于最小值来说，它所在数组的数量是可以计算出来的。
例如1：对于1来说，在元素组种，往左找第一个小于等于它的数字的的索引，没有的话返回-1，
往右找第一个小于它的数字的索引，没有返回数组长度。
最后是有计算公式的：（右索引-1的索引） *（1索引-左索引）

class Solution {
public:
/**
* @param A: an array
* @return: the sum of subarray minimums
*/
int sumSubarrayMins(vector<int> &A) {
// Write your code here.
int res = 0, n = A.size(), mod = 1e9 + 7, j, k;
stack<int> s;
for (int i = 0; i <= n; ++i) {
while (!s.empty() && A[s.top()] > (i == n ? 0 : A[i])) {
j = s.top(), s.pop();
k = s.empty() ? -1 : s.top();
res = (res + A[j] * (i - j) * (j - k)) % mod;
}
s.push(i);
}
return res;
}
};