单调栈-子数组的最小值之和

在这里插入图片描述

代码求解

利用严格的大压小单调栈，找到每个位置数字左右两边离它最近且比它小的数字，确定以该数字为最小值的子数组的范围，通过计算开头和结尾的可能性确定字数租的个数，乘以该数字得到这部分子数组的最小值之和，每个数在弹出的时候都需要计算答案。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    public static int MAXN = 30001;
	public static int MOD = 1000000007;
	public static int[] stack = new int[MAXN];
	public static int r;

	public static int sumSubarrayMins(int[] arr){
		long ans = 0;
		for(int i=0;i<arr.length;i++){
			while(r>0&&arr[stack[r-1]]>=arr[i]){
				int cur = stack[--r];
				int left = r==0?-1:stack[r-1];
				ans = (ans+(long)(cur-left)*(i-cur)*arr[cur])%MOD;
			}
			stack[r++]=i;
		}

		while(r>0){
			int cur = stack[--r];
			int left = r==0?-1:stack[r-1];
			ans = (ans+(long)(cur-left)*(arr.length-cur)*arr[cur])%MOD;
		}
		return (int)ans;
	}
}