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

import java.util.*;
import java.util.stream.IntStream;

/**
 * NC386 子数组的最小值之和
 * @author d3y1
 */
public class Solution {
    private final int MOD = 1000000007;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @return int整型
     */
    public int sumSubarr (ArrayList<Integer> nums) {
        int[] iNums = nums.stream().mapToInt(Integer::intValue).toArray();
        // int[] iNums = nums.stream().mapToInt(i->i).toArray();
        // return solution1(iNums);
        return solution2(iNums);
    }

    /**
     * 动态规划 + 单调栈
     *
     * 举例子找规律:
     * nums数组
     * 0  1  2  3  4  5  6  7  8  9  10
     * 23 43 18 16 35 23 6  11 6  33 30
     *
     * leftMap(i)  表示当前元素nums[i]左边第一个小于当前元素的元素索引 -1:表示没找到(当前元素左边都比当前元素大)
     * rightMap(i) 表示当前元素nums[i]右边第一个小于当前元素的元素索引  N:表示没找到(当前元素右边都比当前元素大)
     *      i       0  1  2  3  4  5  6  7  8  9  10
     * leftMap(i)  -1  0 -1 -1  3  3 -1  6 -1  8  8
     * rightMap(i)  2  2  3  6  5  6  11 8  11 10 11
     *
     * dp[i]表示以元素nums[i]为开头的所有连续子数组的最小值的和
     *    i    0  1  2  3  4  5  6  7  8  9  10
     * dp[0]   23 23 18 16 16 16 6  6  6  6  6
     * dp[1]      43 18 16 16 16 6  6  6  6  6
     * dp[2]         18 16 16 16 6  6  6  6  6
     * dp[3]            16 16 16 6  6  6  6  6
     * dp[4]               35 23 6  6  6  6  6
     * dp[5]                  23 6  6  6  6  6
     * dp[6]                     6  6  6  6  6
     * dp[7]                        11 6  6  6
     * dp[8]                           6  6  6
     * dp[9]                              33 30
     * dp[10]                                30
     *
     * dp[i] = nums[i]*(rightMap.get(i)-i)+dp[rightMap.get(i)]
     * 
     * @param nums
     * @return
     */
    private int solution1(int[] nums){
        int N = nums.length;

        Map<Integer, Integer> rightMap = new HashMap<>();
        Stack<Integer> rightStack = new Stack<>();
        int num;
        // 右边 降序
        for (int i=N-1; i>=0; i--){
            // 找到当前元素右边第一个小于当前元素的元素索引 N:表示没找到, 当前元素右边都比当前元素大
            num = nums[i];
            // 单调增
            while (!rightStack.isEmpty() && num<=nums[rightStack.peek()]){
                rightStack.pop();
            }
            rightMap.put(i, rightStack.isEmpty() ? N : rightStack.peek());
            rightStack.push(i);
        }

        int sum = 0;
        int[] dp = new int[N+1];
        for(int i=N-1; i>=0; i--){
            dp[i] = nums[i]*(rightMap.get(i)-i)+dp[rightMap.get(i)];
            sum = (sum+dp[i]) % MOD;
        }
        
        return sum;
    }

    /**
     * 动态规划 + 单调栈
     *
     * 举例子找规律:
     * nums数组
     * 0  1  2  3  4  5  6  7  8  9  10
     * 23 43 18 16 35 23 6  11 6  33 30
     *
     * leftMap(i)  表示当前元素nums[i]左边第一个小于当前元素的元素索引 -1:表示没找到(当前元素左边都比当前元素大)
     * rightMap(i) 表示当前元素nums[i]右边第一个小于当前元素的元素索引  N:表示没找到(当前元素右边都比当前元素大)
     *      i       0  1  2  3  4  5  6  7  8  9  10
     * leftMap(i)  -1  0 -1 -1  3  3 -1  6 -1  8  8
     * rightMap(i)  2  2  3  6  5  6  11 8  11 10 11
     *
     * dp[i]表示以元素nums[i]为结尾的所有连续子数组的最小值的和
     *    i    0  1  2  3  4  5  6  7  8  9  10
     * dp[0]   23
     * dp[1]   23 43
     * dp[2]   18 18 18
     * dp[3]   16 16 16 16
     * dp[4]   16 16 16 16 35
     * dp[5]   16 16 16 16 23 23
     * dp[6]   6  6  6  6  6  6  6
     * dp[7]   6  6  6  6  6  6  6  11
     * dp[8]   6  6  6  6  6  6  6   6  6
     * dp[9]   6  6  6  6  6  6  6   6  6 33
     * dp[10]  6  6  6  6  6  6  6   6  6 30 30
     *     
     *         { nums[i]*(i-leftMap.get(i))                       , leftMap.get(i) == -1
     * dp[i] = {
     *         { nums[i]*(i-leftMap.get(i)) + dp[leftMap.get(i)]  , leftMap.get(i) != -1
     *
     * @param nums
     * @return
     */
    private int solution2(int[] nums){
        int N = nums.length;

        Map<Integer, Integer> leftMap = new HashMap<Integer, Integer>();
        Stack<Integer> leftStack = new Stack<>();
        int num;
        // 左边 升序
        for (int i=0; i<N; i++){
            // 找到当前元素左边第一个小于当前元素的元素索引 -1:表示没找到, 当前元素左边都比当前元素大
            num = nums[i];
            // 单调增
            while (!leftStack.isEmpty() && num<=nums[leftStack.peek()]){
                leftStack.pop();
            }
            leftMap.put(i, leftStack.isEmpty() ? -1 : leftStack.peek());
            leftStack.push(i);
        }

        int sum = 0;
        int[] dp = new int[N];
        for(int i=0; i<N; i++){
            dp[i] = nums[i]*(i-leftMap.get(i));
            if(leftMap.get(i) != -1){
                dp[i] += dp[leftMap.get(i)];
            }
            sum = (sum+dp[i]) % MOD;
        }
        
        return sum;
    }
}