图解LeetCode——907. 子数组的最小值之和（难度：中等

一、题目

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

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

二、示例

2.1> 示例 1：

【输入】arr = [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。

2.2> 示例 2：

【输入】arr = [11,81,94,43,3]
【输出】444

提示：

• 1 <= arr.length <= 3 * 10^4
• 1 <= arr[i] <= 3 * 10^4

三、解题思想

3.1> 概述

首先根据题意，我们需要做到如下3个步骤：

【步骤1】 找到数组arr的所有子序列。
【步骤2】对比每个子序列内部的整数，并找到每个子序列的最小值。
【步骤3】将这些最小值相加。

但是，如果我们真的按照上面3个步骤去编码的话，会造成程序计算超时。那么就需要我们再去找出更“巧”的方法对这道题进行解答。如果我们仔细分析，其实可以将解题步骤简化为2个步骤：

【步骤1】分别以数组arr中的每个整数作为一个中心点，然后分别去找基于这个中心点的“辐射区域”，要满足在辐射区域内，这个中心点整数值是最小的。例如：在数组[1,3,4,2,6,1]中，如果以整数2为一个中心点，那么它的辐射区域为[3,4,2,6]。问题1：如何快速确定某个中心点的辐射区？
【步骤2】因为在辐射区内，中心点最小，所以计算在辐射区域内，能组成多少个包含中心点的子序列。例如：[3,4,2,6]可以有如下包含中心点2的子序列：[3,4,2]、[3,4,2,6]、[4,2]、[4,2,6]、[2]、[2,6]这6个子序列。那么这个最小值2的总和就是 2 * 6 = 12。问题2：如何计算出包含中心点的子序列个数？

3.2> 问题2：如何计算出包含中心点的子序列个数？

通过上面的简化步骤，我们又引出了2个问题需要处理，那么我们先处理简单一点的问题2，即：如何计算出包含中心点的子序列个数？可以得出如下公式，即：(index(中心点) - index(辐射区第1个整数) + 1) * (index(辐射区最后1个整数) - index(中心点) + 1)。具体详情请见下图：

3.3> 问题1：如何快速确定某个中心点的辐射区？

针对问题1，我们可以采用单调栈的方式，因为计算辐射区内的子序列时，是需要通过下标计算的，所以堆栈中存储的是数组arr中元素的下标。然后，遍历整个数组arr，如果堆栈为空，那么直接入栈；如果堆栈不为空，则进行如下操作：

如果栈顶元素 > arr[i] ：则弹出栈顶元素n，那么针对于这个n来说，它的辐射区域就是(新的栈顶元素, i)[注]左开右开区间。
如果栈顶元素 <= arr[i] ：则arr[i]直接入栈。

具体详情请见下图：

【解释】堆栈stack中存储的是arr中元素对应的下标，在上图中，例如：元素“3”，下标用index(3)=1表示。

针对上面图例所示，我们已经遍历完所有arr数组中的元素了，并且由于4和3都大于2，所以执行了出栈操作，并分别计算了以4和3为中心点的最小值和分别是：4 和 6。但是堆栈中依然还有元素1,2和6，如果不让他们出栈的话，最终结果肯定是错误的。那怎么让他们出栈呢？根据题目中【提示】部分描述，1 <= arr[i] <= 3 * 10^4,所以，arr数组中所有元素都是大于0的，那么我们就虚拟一个元素将其放入堆栈中，因为堆栈中所有元素都小于0，所以也就都会被执行出栈操作了。具体详情请见下图：

最终我们可以得出如下结果：

以“1”为中心点：最小值和等于5。
以“3”为中心点：最小值和等于6。
以“4”为中心点：最小值和等于4。
以“2”为中心点：最小值和等于12。
以“6”为中心点：最小值和等于6。
【最终结果】5+6+4+12+6 = 33。

四、代码实现

class Solution {
    public int sumSubarrayMins(int[] arr) {
        long result = 0;
        int[] stack = new int[arr.length]; // 使用数组结构模拟堆栈，里面存储arr数组的下标，为了便于计算“管辖区域”的跨度
        int head = 0, tail = head, mod = (int) (1e9 + 7); // 配合模拟堆栈的head指针和tail指针
        for (int i = 0; i <= arr.length; i++) {
            int num = (i == arr.length) ? 0 : arr[i]; // 如果arr数组遍历到最后一个元素，则还需要模拟结尾元素0，为了让stack中元素都出栈
            while (head != tail && arr[stack[tail - 1]] > num) {
                int n = stack[--tail]; // 待计算数字arr[n]的【数组下标】
                int h = (head != tail) ? stack[tail - 1] : -1; // arr[n]的“辐射区域”head头的【数组下标】（开区间）
                int t = i; // arr[n]的“辐射区域”tail尾的【数组下标】（开区间）
                result = (result + (long) (n - h) * (t - n) * arr[n]) % mod;
            }
            stack[tail++] = i;
        }
        return (int) result;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o)/ ~ 「干货分享，每天更新」