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。

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-907-sum-of-subarray-minimums-解题思路分析/