题目：子数组的最小值之和

• 给定一个整数数组 A，找到min(B)的总和，其中 B 的范围为A的每个（连续）子数组。
• 由于答案可能很大，因此返回答案模 10^9 + 7。

示例：

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

提示：

• 1 <= A <= 30000
• 1 <= A[i] <= 30000

来源：力扣（LeetCode）第907题

链接：https://leetcode-cn.com/problems/sum-of-subarray-minimums

分析：

• 我们要找到所有子数组的最小值之和，就要找到当每个数作为最小数时这样的子数组有多少个。
• 既然是子树组，那一定是连续的，这题一开始以为可以使用动态规划，结果数据量很大，显然dp会超时。
• 我们先找当这个数为最小数时最大的子数组是多少。也就是说以这个数i开始，它的左边和右边第一个比它小的数，中间这段就是最长的子数组。
• 这一段子数组中的每一个子数组都是以i为最小数的子数组。那这一段的子数组又有多少个子数组呢，以i这个下标为分割线，将(i - left[i]) * (right[i ]- i) * A[i],前两个是子数组的个数，最后那个是子数组的最小值。
• 那现在的问题是如果找到left[]和right[]的值。left和right的值是某一个数的左边和右边最小的那个数在A中的下标。
• 我们可以使用单调栈在O(n)的时间复杂度下找到。

代码：

class Solution {
    public int sumSubarrayMins(int[] A) {
        long mod = (long)1e9 + 7;
        int len = A.length;
        Stack<Integer> stack = new Stack();
        int[] left = new int[len], right = new int[len];
        for (int i = 0; i < len; i++) {
            while (stack.size() > 0 && A[stack.peek()] > A[i]) stack.pop();
            left[i] = stack.size() > 0 ? stack.peek() : -1;
            stack.push(i);
        }
        stack.clear();
        for (int i = len - 1; i >= 0; i--) {
            while (stack.size() > 0 && A[stack.peek()] >= A[i]) stack.pop();
            right[i] = stack.size() > 0 ? stack.peek() : len;
            stack.push(i);
        }
        long ans = 0;
        for (int i = 0; i < len; i++)
            ans += (i - left[i]) * (right[i] - i) * A[i];
        return (int)(ans % mod);
    }
}