题解 | #子数组的最小值之和#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int sumSubarr(ArrayList<Integer> nums) {
        int mod = 1000000007;   // 题目要求的取余数
        int[] dp = new int[nums.size()]; // 用于存储"第i个数为结尾的所有子数组的最小值之和", 共有i+1个子数组以第i个数为末尾
        int sum = 0;
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = 0; i < nums.size(); i++) {
            while (!stack.isEmpty() && nums.get(stack.peek()) >= nums.get(i)) {
                stack.pop();
            }
            // j 是前面第一个小于当前数字的数字到当前数字的【距离】, 也是以第i个数为末尾的子数组中第i个数为最小值的子数组的个数
            int j = stack.isEmpty() ? i + 1 : i - stack.peek();
            // 第i个数为结尾的所有子数组的最小值之和,等于 它自己作为最小值时的所有子数组之和 + 其前面第一个小于它的数为末尾的所有子数组的最小值之和
            dp[i] = nums.get(i) * j + (stack.isEmpty() ? 0 : dp[i - j]);
            stack.push(i);
        }
        for (int i = 0; i < nums.size(); i++) {
            sum = (sum + dp[i]) % mod;
        }
        return sum % mod;
    }
}