一、题目

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<int>& 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。

抽象化：
$i$ 位置的 $x$​，左边离它最近的是比它小的 $k$ 位置的 $y$​， 右边离它最近比它小的是 $j$ 位置的 $z$​，以 $x$ 为最小值的范围为 $(k,j)$，那么产生以 $x$ 为最小值的子数组数量为 $(i-k)\ast (j-i)$​，以 $i$ 位置的 $x$ 值为最小值产生的子数组的累加和为 $(i-k)\ast (j-i)\ast 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 ~ 6
    	 2 ~ 3，2 ~ 4, 2 ~ 5, 2 ~ 6
    		3 ~ 3, 3 ~ 4, 3 ~ 5, 3 ~ 6
而 7 位置的 3 作为最小值，能扩充的范围为 1 ~ 10，所以产生的子数组为：
     1 ~ 7， 1 ~ 8， 1~ 9, 1 ~ 10
    	2 ~ 7， 2 ~ 8， 2 ~ 9， 2 ~ 10
    		......
    		7 ~ 7, 7 ~ 8, 7 ~ 9,  7 ~ 10
    注意，这个3是包含了前面的3的范围的

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

同理，也可以在左边值相等的时候停住：

2、时间复杂度

$O(n)$

3、代码详解

C++版

class Solution {
public:
    int sumSubarrayMins(vector<int>& 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<int> &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]，位置在x
		int[] left = leftNearLessEqual2(arr);
		// right[i] = y : arr[i]右边，离arr[i]最近，< arr[i],的数，位置在y
		int[] 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("测试结束");
	}
}