题目
给定一个数组arr，返回所有子数组最小值的累加和。
力扣链接：子数组的最小值之和
题解
如上图，运用单调栈结构，左边比7小的且离它最近的位置是5，右边离它最近的且小于7的位置是15，所以以7为最小值的子数组分别有，6位置开头：6 ~ 10、6 ~ 11、6 ~ 12、6 ~ 13、6 ~ 14；7位置开头：7 ~ 10、7 ~ 11、7 ~ 12、7 ~ 13、7 ~ 14；8位置开头：8 ~ 10、8 ~ 11、8 ~ 12、8 ~ 13、8 ~ 14；9位置开头：9 ~ 10、9 ~ 11、9 ~ 12、9 ~ 13、9 ~ 14；10位置开头：10 ~ 10、10 ~ 11、10 ~ 12、10 ~ 13、10 ~ 14；所以整体子数组个数是25个（其实就是开头位置的个数 * 结尾位置的个数），每个子数组的最小值都是7，那么以7做最小值的所有子数组的累计和就是 25 * 7。
具体可以带入如下例子：
接下来推广一下，得到公式：( i - k ) * ( j - i ) * x（因为k位置和j位置都是到不了的！！！）
但是，以上讨论的都是认为数组没有重复值的情况！！！有重复值的话，讨论起来是挺复杂的！！！
如何计算以3位置上的3为最小值的所有子数组的数量？
1位置开头：1 ~ 3、1 ~ 4、1 ~ 5、1 ~ 6；
2位置开头：2 ~ 3、2 ~ 4、2 ~ 5、2 ~ 6；
3位置开头：3 ~ 3、3 ~ 4、3 ~ 5、3 ~ 6；
如何计算以7位置上的3为最小值的所有子数组的数量？
开头位置有变化！！！1 ~ 6位置整体属于开头位置。
1 ~ 7、1 ~ 8、1 ~ 9、1 ~ 10；
2 ~ 7、2 ~ 8、2 ~ 9、2 ~ 10；
…
7 ~ 7、7 ~ 8、7 ~ 9、7 ~ 10；
如何计算以11位置上的3为最小值的所有子数组的数量？
那么开头位置就是：1 ~ 10整体范围
计算以13位置上的3为最小值的所有子数组的数量也同理可得
package com.harrison.class14;
/** * @author Harrison * @create 2022-03-27-15:06 * @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。 */
public class Code06_SumOfSubarrayMinimums {
public static int sumSubarrayMins1(int[] arr){
int sum=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]);
}
sum+=min;
}
}
return sum;
}
public static int sumSubarrayMins2(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];
int end=right[i]-i;
ans+=start*end*arr[i];
}
return ans;
}
public static int[] leftNearLessEqual2(int[] arr){
int[] left=new int[arr.length];
for(int i=0; i<arr.length; 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;
}
public static int[] rightNearLess2(int[] arr){
int[] right=new int[arr.length];
for(int i=0; i<arr.length; i++){
int ans=arr.length;
for(int j=i+1; j<arr.length; j++){
if(arr[j]<arr[i]){
ans=j;
break;
}
}
right[i]=ans;
}
return right;
}
public static int sumSubarrayMins3(int[] arr){
int[] stack=new int[arr.length];
// left[i]==x：arr[i]左边，离arr[i]最近，小于等于arr[i]的数的位置在x，如果没有x就是-1
// right[i]==y，arr[i]右边，离arr[i]最近，小于arr[i]数的位置在y，如果没有y就是-1
int[] left=leftNearLessEqual3(arr,stack);
int[] right=rightNearLess3(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[] leftNearLessEqual3(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[] rightNearLess3(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[i]<arr[stack[size-1]]){
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 = sumSubarrayMins1(arr);
int ans2 = sumSubarrayMins2(arr);
int ans3 = sumSubarrayMins3(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("测试结束");
}
}
文章评论