907-子数组的最小值之和

题目

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

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

示例 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

提示：

• 1 <= arr.length <= 3 * 104
• 1 <= arr[i] <= 3 * 104

思路

用一个栈保存到达i位置时左侧更小值的位置。

dp：以arr[i]为结尾的所有数组的最小值之和。

dp[i+1] = (dp[s.top()+1]+(i-s.top())*arr[i])

dp[s.top()+1]表示s.top()以及之前的所有数组，其数组最小值都是比arr[i]小的，所以前面的延伸到当前arr[i]，最小值不变，其和不变。

(i-s.top())*arr[i]表示以arr[i]为结尾并且以arr[i]为最小值的数组的和。

代码

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int* dp = new int[arr.size()+1];
        int* stack = new int[arr.size()+1];
        memset(dp,0,sizeof(int)*(arr.size()+1));
        memset(stack,0,sizeof(int)*(arr.size()+1));
        int top=-1;
        int mod = 1000000007;
        stack[++top]=-1;
        for(int i=0;i<arr.size();++i){
            while(top>0&&arr[i]<=arr[stack[top]]) top--;
            dp[i+1] = (dp[stack[top]+1]+(i-stack[top])*arr[i])%mod;
            stack[++top]=i;
        }
        int res = 0;
        for(int i=0;i<=arr.size();++i){
            res=(res + dp[i])%mod;
        }
        return res;
    }
};