一、题目

1、题目描述

给定一个整数数组 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

2、基础框架

class Solution {
public:int sumSubarrayMins(vector& arr) {}
};

3、原题链接

907.子数组的最小值之和

二、解题报告

1、思路分析

整体思路：

求的以每个位置的值为最小值能得到的子数组个数。

流程：
假设 10 位置是 7， 左边离它最近比它小的是 5 位置的 5，右边离它最近比它小的是 15 位置的 4。那么以 7 作为最小值的子数组范围为 6 ~ 14，但这个范围中并不是所有的子数组都是以 7 作为最小值的，比如假设 6 位置是 10， 7 位置是 8，那么6位置作为子数组最小值是10，7位置作为子数组的最小值是8，所以必须要跨过 10 位置的 7 的子数组才是以 7 作为最小值的。

示例：

以 6 位置开头的：6 ~ 10、6 ~ 11、6 ~ 12、6 ~ 13、6 ~ 14 这些都是以 7 作为最小值的子数组。

同理还有 7 位置开头的，8 位置开头的，9 位置开头的，10 位置开头的子数组。

那么整体数量是多少呢？

6 ~ 10 共 5 个数，10 ~ 14 共 5 个数，所以总的以 7 为最小值的子数组个数为 5 * 5 = 25 个，产生的子数组最小值累加和为 25 * 7 = 175。

抽象化：
iii 位置的 xxx​，左边离它最近的是比它小的 kkk 位置的 yyy​， 右边离它最近比它小的是 jjj 位置的 zzz​，以 xxx 为最小值的范围为 (k,j)(k, j)(k,j)，那么产生以 xxx 为最小值的子数组数量为 (i−k)∗(j−i)(i−k) ∗ (j−i)(i−k)∗(j−i)​，以 iii 位置的 xxx 值为最小值产生的子数组的累加和为 (i−k)∗(j−i)∗x(i−k)∗(j−i)∗x(i−k)∗(j−i)∗x
​
有重复值的情况需要改进：

数组：2 4 5 3 6 6 6 3 7 8 6  3  5  3  2
下标：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14那么以 3 位置的 3 作为最小值，能扩充的范围为 1 ~ 6, 产生的子数组为：1 ~ 3，1 ~ 4, 1 ~ 5，1 ~ 62 ~ 3，2 ~ 4, 2 ~ 5, 2 ~ 63 ~ 3, 3 ~ 4, 3 ~ 5, 3 ~ 6
而 7 位置的 3 作为最小值，能扩充的范围为 1 ~ 10，所以产生的子数组为：1 ~ 7， 1 ~ 8， 1~ 9, 1 ~ 102 ~ 7， 2 ~ 8， 2 ~ 9， 2 ~ 10......7 ~ 7, 7 ~ 8, 7 ~ 9,  7 ~ 10注意，这个3是包含了前面的3的范围的

就是结尾处在相等位置的时候停住，目的是为了去重。

2、时间复杂度

O(n)O(n)O(n)

3、代码详解

C++版

class Solution {
public:int sumSubarrayMins(vector& arr) {if (arr.size() == 0) return 0;long ans = 0;int left[arr.size()];int right[arr.size()];memset(left, 0, sizeof(left));memset(right, 0, sizeof(right));nearLessLeftAndLessEqualRight(arr, left, right);for (int i = 0; i < arr.size(); i++) {int start = i - left[i]; //子数组起点个数int end = right[i] - i; //子数组终点个数ans += start * end * (long) arr[i];ans %= 1000000007;}return ans;}// 左边 < arr[i], 右边 >= arr[i] 的位置构成的范围void nearLessLeftAndLessEqualRight(vector &arr, int *left, int *right) {int n = arr.size();int _stack[n];int si = -1;for (int i = 0; i < n; i++) {while (si != -1 && arr[_stack[si]] >= arr[i]) {int cur = _stack[si--];left[cur] = si == -1 ? -1 : _stack[si];right[cur] = i;}_stack[++si] = i;}while (si != -1) {int cur = _stack[si--];left[cur] = si == -1 ? -1 : _stack[si];right[cur] = n;}}
};

Java版

// 测试链接：https://leetcode.com/problems/sum-of-subarray-minimums/
// subArrayMinSum1是暴力解
// subArrayMinSum2是最优解的思路
// sumSubarrayMins是最优解思路下的单调栈优化
// Leetcode上不要提交subArrayMinSum1、subArrayMinSum2方法，因为没有考虑取摸
// Leetcode上只提交sumSubarrayMins方法，时间复杂度O(N)，可以直接通过
public class SumOfSubarrayMinimums {public static int subArrayMinSum1(int[] arr) {int ans = 0;for (int i = 0; i < arr.length; i++) {for (int j = i; j < arr.length; j++) {int min = arr[i];for (int k = i + 1; k <= j; k++) {min = Math.min(min, arr[k]);}ans += min;}}return ans;}// 没有用单调栈public static int subArrayMinSum2(int[] arr) {// left[i] = x : arr[i]左边，离arr[i]最近，<=arr[i]，位置在xint[] left = leftNearLessEqual2(arr);// right[i] = y : arr[i]右边，离arr[i]最近，< arr[i],的数，位置在yint[] right = rightNearLess2(arr);int ans = 0;for (int i = 0; i < arr.length; i++) {int start = i - left[i]; //i位置左边能扩充的范围中的数字个数int end = right[i] - i; //i位置右边能扩充的范围中的数字个数ans += start * end * arr[i];}return ans;}public static int[] leftNearLessEqual2(int[] arr) {int N = arr.length;int[] left = new int[N];for (int i = 0; i < N; i++) {int ans = -1;for (int j = i - 1; j >= 0; j--) {if (arr[j] <= arr[i]) {ans = j;break;}}left[i] = ans;}return left;}// 比如两个位置的3，后一个位置的3往左边扩充的区域到前一个位置的3停止（到不了）public static int[] rightNearLess2(int[] arr) {int N = arr.length;int[] right = new int[N];for (int i = 0; i < N; i++) {int ans = N;for (int j = i + 1; j < N; j++) {if (arr[i] > arr[j]) {ans = j;break;}}right[i] = ans;}return right;}//O(n)public static int sumSubarrayMins(int[] arr) {int[] stack = new int[arr.length];int[] left = nearLessEqualLeft(arr, stack);//每个位置左边离它最近 <= 它的位置int[] right = nearLessRight(arr, stack); 每个位置右边离它最近 < 它的位置long ans = 0;for (int i = 0; i < arr.length; i++) {long start = i - left[i];long end = right[i] - i;ans += start * end * (long) arr[i];ans %= 1000000007;}return (int) ans;}public static int[] nearLessEqualLeft(int[] arr, int[] stack) {int N = arr.length;int[] left = new int[N];int size = 0;for (int i = N - 1; i >= 0; i--) {while (size != 0 && arr[i] <= arr[stack[size - 1]]) {left[stack[--size]] = i;}stack[size++] = i;}while (size != 0) {left[stack[--size]] = -1;}return left;}public static int[] nearLessRight(int[] arr, int[] stack) {int N = arr.length;int[] right = new int[N];int size = 0;for (int i = 0; i < N; i++) {while (size != 0 && arr[stack[size - 1]] > arr[i]) {right[stack[--size]] = i;}stack[size++] = i;}while (size != 0) {right[stack[--size]] = N;}return right;}public static int[] randomArray(int len, int maxValue) {int[] ans = new int[len];for (int i = 0; i < len; i++) {ans[i] = (int) (Math.random() * maxValue) + 1;}return ans;}public static void printArray(int[] arr) {for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}public static void main(String[] args) {int maxLen = 100;int maxValue = 50;int testTime = 100000;System.out.println("测试开始");for (int i = 0; i < testTime; i++) {int len = (int) (Math.random() * maxLen);int[] arr = randomArray(len, maxValue);int ans1 = subArrayMinSum1(arr);int ans2 = subArrayMinSum2(arr);int ans3 = sumSubarrayMins(arr);if (ans1 != ans2 || ans1 != ans3) {printArray(arr);System.out.println(ans1);System.out.println(ans2);System.out.println(ans3);System.out.println("出错了！");break;}}System.out.println("测试结束");}
}