子数组的最小值之和

# -*- coding: utf-8 -*-

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/a7401d0dd4ec4071a31fd434e150bcc2?tpId=196&tqId=40517&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    参考：
        https://leetcode.cn/problems/sum-of-subarray-minimums/solution/zi-shu-zu-de-zui-xiao-zhi-zhi-he-by-leetcode/
    算法：
        对于每个 j，考虑所有子序列 [i, j] 的最小值。想法是每当我们增加 j，这些最小值可能会有关联，事实上，min(A[i:j+1]) = min(A[i:j], A[j+1])。
        我们维护最小值栈stack，stack中存储的元素为(x, c)，表示以x为结尾且x为最小值的区间个数，stack按照x单调递增。枚举区间右端点j，弹出栈中 x >= y的元素，因为这些以x结尾且以x为最小值的区间，尾部追加y之后，变成以y结尾且以y为最小值的区间了。另外我们使用Sum来记录以当前元素y结尾的所有区间的最小值之和。
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(n)
    """

    def sumSubarr(self, nums):
        # write code here
        MOD = 10 ** 9 + 7
        ans, Sum, stack = 0, 0, []

        for j, y in enumerate(nums):
            count = 1
            while stack and stack[-1][0] >= y:
                x, c = stack.pop() # 以元素x结尾的区间个数为c，现在我们将元素y作为这些区间的尾部，也就是之前c个以元素x为最小值的区间 变为 以元素y作为最小值的区间
                count += c
                Sum -= x * c # dot始终记录以当前元素y结尾的所有区间的最小值之和
            stack.append((y, count)) # count表示以元素y结尾且y作为区间最小值的区间个数
            Sum += y * count
            ans += Sum # 累加以y结尾的所有区间的最小值之和

        return ans % MOD

if __name__ == "__main__":
    sol = Solution()

    # nums = [3, 1, 2, 4, 5]

    # nums = [3, 1, 2, 4]

    # nums = [11, 81, 94, 43, 3]

    nums = [1, 2]

    # nums = [3, 2, 1]

    res = sol.sumSubarr(nums)

    print res

import java.util.*;

public class Solution {
    public int sumSubarr (ArrayList<Integer> nums) {
        // 枚举nums[j]为最小数：向左向右找第一个更小的

        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1); // 左侧更小的默认下标-1
        long res = 0, n = nums.size();
        for (int k = 0; k <= n; k++) {
            int x = k < n ? nums.get(k) : -1; // 右侧更小的默认下标n
            while (stack.size() > 1 && nums.get(stack.peek()) > x) {
                int j = stack.pop();
                int i = stack.peek();
                res += 1L * nums.get(j) * (k - j) * (j - i); // 包含nums[j]的子数组
                res %= 1000_000_007;
            }
            stack.push(k);
        }
        return (int)res;
    }
}

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