Monotonic stack structure exercise -- cumulative sum of minimum values of subarrays

subject

Given an array arr, Returns the cumulative sum of the minimum values of all subarrays .

Force link ： The sum of the minimum values of a subarray

Answer key

Pictured above , Use monotonic stack structure , On the left 7 The small and nearest position is 5, The right side is closest to it and less than 7 The position is 15, So 7 The subarrays with minimum values are ,6 Start of position ：6 ~ 10、6 ~ 11、6 ~ 12、6 ~ 13、6 ~ 14;7 Start of position ：7 ~ 10、7 ~ 11、7 ~ 12、7 ~ 13、7 ~ 14;8 Start of position ：8 ~ 10、8 ~ 11、8 ~ 12、8 ~ 13、8 ~ 14;9 Start of position ：9 ~ 10、9 ~ 11、9 ~ 12、9 ~ 13、9 ~ 14;10 Start of position ：10 ~ 10、10 ~ 11、10 ~ 12、10 ~ 13、10 ~ 14; So the total number of subarrays is 25 individual （ In fact, it is the number of starting positions * Number of end positions ）, The minimum value of each subarray is 7, So in order to 7 The cumulative sum of all subarrays making the minimum is 25 * 7.

Specific examples can be brought in as follows ：

Next, promote , Get the formula ：( i - k ) * ( j - i ) * x（ because k Location and j The position is unreachable ！！！）

however , The above discussion is all about the case that the array has no duplicate values ！！！ If there are duplicate values , The discussion is quite complicated ！！！

How to calculate to 3 In position 3 The number of all subarrays that are the minimum ？
1 Start of position ：1 ~ 3、1 ~ 4、1 ~ 5、1 ~ 6;
2 Start of position ：2 ~ 3、2 ~ 4、2 ~ 5、2 ~ 6;
3 Start of position ：3 ~ 3、3 ~ 4、3 ~ 5、3 ~ 6;

How to calculate to 7 In position 3 The number of all subarrays that are the minimum ？
The beginning position has changed ！！！1 ~ 6 The whole position belongs to the starting position .
1 ~ 7、1 ~ 8、1 ~ 9、1 ~ 10;
2 ~ 7、2 ~ 8、2 ~ 9、2 ~ 10;
…
7 ~ 7、7 ~ 8、7 ~ 9、7 ~ 10;

How to calculate to 11 In position 3 The number of all subarrays that are the minimum ？
Then the beginning position is ：1 ~ 10 Overall scope

Calculate with 13 In position 3 The same can be said for the number of all subarrays that are the minimum

package com.harrison.class14;

/** * @author Harrison * @create 2022-03-27-15:06 * @motto  looking for him for thousand times in the crowd , Suddenly look back , The man was in the dim light . */
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] On the left , leave arr[i] lately ,<=arr[i], Position in x
        int[] left=leftNearLessEqual2(arr);
        // right[i] = y : arr[i] On the right , leave arr[i] lately ,< arr[i], Number of numbers , Position in 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] On the left , leave arr[i] lately , Less than or equal to arr[i] The position of the number of is x, without x Namely -1
        // right[i]==y,arr[i] On the right , leave arr[i] lately , Less than arr[i] The position of the number is y, without y Namely -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];//  Calculate a starting number at the unreachable position on the left 
            long end=right[i]-i;//  Calculate an ending number at the unreachable position on the right 
            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(" Beginning of the test ");
        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(" Something went wrong ！");
                break;
            }
        }
        System.out.println(" End of test ");
    }
}