leetcode 907. Sum of Subarray Minimums 解题思路分析

题目大意:

子数组的最小值之和

给定一个整数数组 A,找到 min(B) 的总和,其中 B 的范围为 A 的每个(连续)子数组。

由于答案可能很大,因此返回答案模 10^9 + 7

示例:

输入:[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。

提示:

  1. 1 <= A <= 30000
  2. 1 <= A[i] <= 30000

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=907

解题思路:

本题是中等难度,在算法上比较巧妙,我们先用一个例子来思考这个问题,比如下面这个数组:

{5, 6, 2, 7, 8, 9}

一目了然,2是数组中最小的数字,如果我们想知道所有包含2的子数组的最小值的和,那么,我们只要知道了包含2的子数组个数,再用个数乘以2就是结果。

如何求出所有包含2的连续子数组个数呢?2左边有2个数比自己大,右边有3个大于自身的数字,再加上2自身,一共6个数字,我们可将2加入到任意一边,将数组拆分为,

{5, 6, 2} {7, 8, 9} 
或者
{5, 6} {2, 7, 8, 9}

以第一种为例,要保证子数组中包含2并且连续的话,左边数组的2是必须存在的,所以左边的组合可能是:

{5, 6, 2} 
{6, 2} 
{2} 

然而右边数组中不包含2,所以会比左边多一种情况:

{7, 8, 9} 
{7, 8} 
{7} 
{} 

因此可以得到包含2的连续子数组个数应该为:

count = length(包含最小值的部分) * (length(不包含最小值的部分) + 1)

验证一下,所有的情况应该如下:

{5, 6, 2}
{5, 6, 2, 7}
{5, 6, 2, 7, 8}
{5, 6, 2, 7, 8, 9}

{6, 2}
{6, 2, 7}
{6, 2, 7, 8}
{6, 2, 7, 8, 9}

{2}
{2, 7}
{2, 7, 8}
{2, 7, 8, 9}

这个例子的思路是本题的核心,如果我们知道了数组中每个数字左右各有多少个比自己大的数字,那么利用上面的公式,就能求出包含当前位所有子数组的最小值(当前位自己)的和。

接下来,问题就变为如何找到当前位左右比自己大的数字的个数。

我们先把数组正向循环一遍,可以与前位比较来得出当前位置左边大于自身的个数。同理再反向循环一遍数组,能够得到当前位置右边比自身大的数字个数。最后再循环一遍,按照公式,把每个位置的和求出,都加在一起即是最终结果。时间复杂度为N*3。

看下完整代码:

public int sumSubarrayMins(int[] A) {
    int[] leftBigger = new int[A.length];
    int[] rightBigger = new int[A.length];
    long sum = 0;
    // 计算左边比自身大的数的个数
    for (int i = 0; i < A.length; i++) {
        int countLeft = 1;
        int j = i - 1;
        while (j >= 0 && A[j] >= A[i]) {
            countLeft += leftBigger[j];
            j -= leftBigger[j];
        }
        leftBigger[i] = countLeft;
    }
    // 计算右边比自身大的数的个数
    for (int i = A.length - 1; i >= 0; i--) {
        int countRight = 1;
        int k = i + 1;
        while (k < A.length && A[k] > A[i]) {
            countRight += rightBigger[k];
            k += rightBigger[k];
        }
        rightBigger[i] = countRight;
    }
    // 算出结果
    for (int i = 0; i < A.length; i++) {
        sum += (A[i] * leftBigger[i] * rightBigger[i]);
    }
    return (int) (sum % 1000000007);
}

本题解法用时8ms。

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-907-sum-of-subarray-minimums-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

leetcode 907. Sum of Subarray Minimums 解题思路分析》有2条回应

  1. Pingback引用通告: leetcode 84. Largest Rectangle in Histogram 解题思路分析 – Leetcode刷题

发表评论

您的电子邮箱地址不会被公开。