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 10^4
1 <= arr[i] <= 3 10^4

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sum-of-subarray-minimums
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

2281的前置题，这个题倒是会做，使用单调栈找出一个数左边和右边第一个比自己小或者大的数，这类题做过不少，比如2104题。

计算完leftFirstLow和rightFirstLow（定义见注释）后，对于一个数arr[i]，其可以作为%20*%20(rightFirstLow%5Bi%5D%20-%20i)#card=math&code=%28i%20-%20leftFirstLow%5Bi%5D%29%20%2A%20%28rightFirstLow%5Bi%5D%20-%20i%29&id=Ml8MD)个子数组的最小值，乘以arr[i]累加到ans中。

代码

代码一

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        Deque<Integer> stack = new ArrayDeque<>();
        // leftFirstLow[i]表示nums[i]左边最近的 "<=nums[i]" 的元素的下标
        int[] leftFirstLow = new int[n];
        // rightFirstLow[i]表示nums[i]右边最近的 "<nums[i]" 的元素的下标
        int[] rightFirstLow = new int[n];
        for (int i = 0; i <= n; i++) {
            int num = i == n ? Integer.MIN_VALUE : arr[i];
            while (!stack.isEmpty() && num < arr[stack.peek()]) {
                int k = stack.pop();
                leftFirstLow[k] = stack.isEmpty() ? -1 : stack.peek();
                rightFirstLow[k] = i;
            }
            stack.push(i);
        }
        long ans = 0;
        int mod = (int) (1e9 + 7);
        for (int i = 0; i < n; i++) {
            // 注意三个数相乘后可能会int溢出，因此
            ans = (ans + (long) arr[i] * (i - leftFirstLow[i]) * (rightFirstLow[i] - i)) % mod;
        }
        return (int) ans;
    }
}

代码二

因为leftFirstLow和rightFirstLow可以一起算出来，所以没必要将这两个数组算出来最后再加，可以直接在循环中计算完leftFirstLow[k]和rightFirstLow[k]后就将k处的贡献累加到ans中。

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        Deque<Integer> stack = new ArrayDeque<>();
        long ans = 0;
        int mod = (int) (1e9 + 7);
        for (int i = 0; i <= n; i++) {
            int num = i == n ? Integer.MIN_VALUE : arr[i];
            while (!stack.isEmpty() && num < arr[stack.peek()]) {
                int k = stack.pop();
                int leftFirstLow = stack.isEmpty() ? -1 : stack.peek();
                ans = (ans + (long) arr[k] * (k - leftFirstLow) * (i - k)) % mod;
            }
            stack.push(i);
        }
        return (int) ans;
    }
}