欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java/907. 子数组的最小值之和

程序员文章站 2022-03-24 17:24:02
...

题目

Java/907. 子数组的最小值之和

 

 

 

代码部分一(389ms)

class Solution {
    long res = 0;                                           
    long mod = 1000000007;                                  // 案模, res % mod 得到溢出后的想要的数
    public int sumSubarrayMins(int[] A) {
        for(int i = 0; i < A.length; i++){
            int l = i - 1;                                 // 向左可延伸多少个子数组(min)
            for( ;l >= 0 && A[i] < A[l]; l--) ;
            int r = i + 1;                                // 向右可延伸多少个子数组(min)
            for( ; r < A.length && A[i] <= A[r]; r++) ;
            res += (i - l) * (r - i) * A[i];              // 当前 A[i]在多少个子数组中最小
        }
        return (int)(res % mod);
    }
}

 

代码部分二(最后一个测试用例超时)

class Solution {
    long res = 0;
    int mod = 1000000007;
    public int sumSubarrayMins(int[] A) {
        for(int i = 0; i < A.length; i++){
            res += A[i];
            for(int j = i + 1; j < A.length && i < A.length - 1; j++){
                res += findMin(A, i, j);
            }
        }
        return (int)(res % mod);
    }
    public long findMin(int[] A, int l, int r){
        long min = A[l];
        for(int i = l + 1; i <= r; i++){
            if(A[i] < min)
                min = A[i];
        }
        return min;
    }
}