leetcode 907. 子数组的最小值之和

题目如下

数据范围

  观察数据范围理论上平方复杂度的算法计算次数逼近1e9还不至于超时，但是由于有mod 1e9导致超时。所以本题不能靠暴力枚举来解决。
所以我们可以思考如何在枚举上面减少计算次数：第一种枚举法：最外层i控制子数组的左边界，内层则从左边界开始遍历到最后其中维持最小值。如此可以枚举完所有的子数组，显然超时。这种枚举法不好在忽略了一个值可能是很多子数组的最小值。例如 在数组[3,1,2,4]中子数组[3,1,2] [1,2]最小值都是1所以不方便减少计算次数。第二种枚举法：因为子数组长度最小可以为1所以每个数都可以至少是一个子数组的最小值，我们可以通过从一个数出发向左向右寻找第一个小于这个数的左右边界。我们只需要算出在这个边界能形成多少个包含i的子数组就可以得到以arr[i]为最小值的子数组的数量。（即从[l,i] [i,r]各自选1个值就行 排列组合的思想）显然也超时，但是很好利用了特性。
所以我们来思考如何减少第二种枚举法的复杂度：因为向左向右寻找的思路一样所以这里就仅说明向左寻找的思路。显然每次向左搜索第一个小于这个数的重复计算太多，我们可以想想几种情况如果数组有(i,j都是下标且i < j)那么我们令i j对应的第一个小于的坐标为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并无关系甚至推广来说只要当前处理的i下标大于j那么因为j排掉的答案并不是i的答案。换句话说我们处理完j以后只需要把j存起来以防万一i的答案是j就行。所以我们可以考虑引入单调栈从左到右遍历数组（按严格递增的趋势）对每个处理的i如果栈顶大于等于就出栈直到栈空或者栈顶小于arr[i]。如此便确定左边界，当然我们采用左开右开的区间方便计算（使用-1作为哨兵）。右边界同理只不过是从右往左遍历这里不多赘述。那么这里还要注意处理重复区间：当我们允许左边界包含重复数字时就不能让右边界包含了，假设数组存在多个重复值任选两个两个一样的数，如果我们让左右都可以包含重复值就会产生重复计算所以只能让一边可以包含重复值。

通过代码

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; }};