我理解的算法 - 907.子数组的最小值之和（单调栈经典例题）

我理解的算法 - 907.子数组的最小值之和（单调栈经典例题）

• • 题目
  • 暴力尝试
  • 找规律优化
  • 单调栈
  • 最终优化

题目

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

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

示例 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：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sum-of-subarray-minimums

暴力尝试

这道题目要说解法，其实一点也不难，暴力的解法应该大家都可以想到，就是把所有的组合的最小值一个一个都加起来即可，代码如下

public int sumSubarrayMins(int[] arr) {long sum = 0;for(int i = 0; i < arr.length; i++){    int minNum = arr[i];    int j = i;    while(j < arr.length){ minNum = Math.min(minNum, arr[j]); sum = (sum + minNum) % 1000000007; j++;    }}return (int) sum;}

妥妥的超时啊有没有，超时原因当然是我们的时间复杂度太高了，并且还用到了取模操作，所以导致了超时也是正常的，那么我们要想其他的解法了

找规律优化

我们想想怎么样才能对上面的代码进行优化呢，从题目上可以看出来似乎有一点规律，如$[3,1,2,4]$这道题目，题目已经把他的所有子数组都列了出来，子数组为$ [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]$，我们不妨分一下类，再来算结果，我们使用贡献分来说明，并且按照每个子数组中的最小的数字进行归类

• 对于3来说，他只有$[3]$这个子序列是对最后结果有贡献的，得3分
• 再来看1，有$[1]，[3,1]，[1,2]，[3,1,2]，[1,2,4]，[3,1,2,4]$ 总共6个，那么就是6个1，即6 * 1 = 6 分
• 2的话，有$[2]，[2,4]$总共2个，2 * 2 = 4分
• 最后4的话只有$[4]$一个，得4分

那么我们最终结果就是$3+6+4+4=17$，看出规律来了吗，即我们只要用当前数字的有效的贡献子数组（即子数组中当前数字为最小就算是1个有效贡献子数组）的个数乘以了当前数字再求一个SUM就是最终结果了，那么 我们只要能够算出来每个数字的有效贡献子数组个数既可以完成计算过程，我们怎么知道呢？

我们不妨再来看一下题目，来看1的情况，我们可以自己脑海里先想象一下，1可以和哪些数字组合，得到最有效的子数组，一起来看一下，

• 我们先把1作为右边界，即从1的左边来数有$[3,1]$
• 再把1作为左边界，即1的右边来组合有$[1,2],[1,2,4]$
• 我们还漏了一种情况，即1在中间的情况，那么有$[3,1,2],[3,1,2,4]$
• 最后不要忘记还有1自己的本身，即$[1]$

那么从上面的分析我们可以得出，对于1来说，就是把这4种组合加起来，即$左边组合个数+右边组合个数+左右结合个数+1$，得到结果为6，那么我们把这个规律带到题目中去

对于左边和右边个数来说，则是看1左边和右边有多少个数比它小即可，而左右结合的个数其实就是$左边个数\ast 右边个数$，这个其实就是一个组合的规律，可以多想一下就会明白，那么我们的公式变为了$左边组合个数+右边组合个数+左边组合个数\ast 右边组合个数+1$，我们可以验证一下，1的左边有1个数满足贡献条件，1的右边有2个数，那么结果是$1+2+1\ast 2+1=6$，答案正确，那么对于3来说我们也可以计算一下，左边没有就是$0$，右边没有也是$0$，即$0+0+0\ast 0+1$，答案为1，正确，其他的也可以验证一下，那么我们的核心公式就有了，另外这个公式不是太美观，我们可以简化这个公式，我们都学过乘法分配律吧，不知道的自己查课本去，哈哈，根据乘法分配律，我们很容易的可以推算出其可以简化为$(左边组合个数十1)\ast (右边组合个数+1)$，好了，这下简单了。

public int sumSubarrayMins(int[] arr) {long ans = 0;for(int i = 0; i < arr.length; i++){    int leftCount = 0;    int rightCount = 0;    int left = i;    int right = i;    while(left > 0 && arr[i] < arr[--left]) leftCount++;    while(right < arr.length - 1 && arr[i] <= arr[++right]) rightCount++;    long sum = (long)(leftCount + 1) * (rightCount + 1) * arr[index];    ans = (ans + sum) % 1000000007;}return (int) ans;}

这样我们可以明显的减少取模操作的次数，但是跑了一下，感觉还是挺慢，怎么办呢，我们看到官网推荐用单调栈来做，那么这个又是如何的思路呢？

单调栈

首先我们需要知道什么是单调栈，单调栈百度一下还是挺好理解的，就是这个栈里面的数值都是单调递增或递减的，拿递增单调栈来说，如果当前要入栈对象比当前栈顶对象大，则直接入栈，如果小的话，则将栈顶弹出，再来比较弹出后栈顶元素与当前对象的大小，以此循环往复即可得到一个单调递增栈，举个例子就明白了，比如我们来尝试用上面的题目来维护一个单调栈的话，$[3,1,2,4]$进行遍历入栈

• 首先栈为空，3直接入栈
• 到1比3小，3出栈，1入栈
• 此时栈顶为1,2比1大，入栈
• 4比1大，也入栈

上面我们就得到了一个$[1,2,4]$的单调递增栈了，那么这个栈搞的这样，弄啥咧？这样有啥用处呢？我们上面的解题的首要思路是要得到当前值的左边界和右边界这样我们可以直接算出来左边个数和右边个数，就能套用我们上面的公式来计算了，单调栈其实正好做了这个事情，我们来分析下上面的步骤对应怎么得出来左右边界的

• 第一步，3入栈没毛病，但是我们不需要把3直接入栈，而是将其下标入栈，即0入栈
• 第二步，通过栈顶的下标，可以得到1比栈顶的3小了，3对应的下标值要出栈了，但是1的下标值先不要急着入栈，等我们将3计算完成再入栈，由于1比3小，所以3的右边界肯定就是这个1了对吧，所以其右边界的index即为1的下标，如果我们在循环遍历中用$i$进行循环，那么就是$i$，那么其左边界也很好理解，就是在它自己出栈后，位于栈顶的元素，这边又由于3出栈后，就没有元素了，所以我们记录为-1，那么我们左右边界的下标都有了，就可以计算左右的个数了，左边的个数就等于$当前出栈的记录的下标-左边界下标-1$，右边的个数就等于了$右边界下标-当前出栈的记录的下标-1$，即$左边个数=0-(-1)-1=0，右边个数=1-0-1=0$, 【注意这边的减1是为了不会把自己这个数也算在个数里面，不然就算多啦，在算个数的时候我们只要看当前数的左右个数即可，因为我们的公式里面最终会带上自己的个数进行计算】，最后套用公式得到结果为$(0+1)\ast (0+1)\ast 3=3$，最后再把1入栈
• 第三步把2入栈
• 第四步把4入栈
• 最后，遍历到上面结束了，栈里面的对象再进行最后的计算，可别忘了栈里面留下的数哈，将其一个个出栈，计算左右边界以及左右个数，套用公式即可，需要注明的是，上面步骤计算右边界的时候，我们使用的是$i$来计算的，那么这边我们需要全部出栈的话，$i$即是整个数组的长度了，因为对于最后存在于栈中的元素来说，他们都是站到最后的，所以他们的右边界肯定都是可以到数组最后的，这边又是单调递增栈的一个好处了，这样我们就算出了最后的结果来了，我们很好的利用了单调栈保存了一组下标，巧妙的计算出了最终结果

public int sumSubarrayMins(int[] arr) {    if (arr == null || arr.length == 0) { return 0;    }    int n = arr.length;    long ans = 0;    Stack<Integer> stack = new Stack<>();    for(int i = 0; i < n; i++){ while(!stack.empty() && arr[i] < arr[stack.peek()]){     ans = (ans + count(stack, i, arr)) % 1000000007; } stack.push(i);    }    while(!stack.empty()){ ans = (ans + count(stack, n, arr)) % 1000000007;    }    return (int) ans;}public int count(Stack<Integer> stack, int curLength, int[] arr){    int index = stack.pop();    int leftIndex = stack.empty() ? -1 : stack.peek();    int rightIndex = curLength;    int leftCount = index - leftIndex - 1;    int rightCount = rightIndex - index - 1;    return (leftCount + 1) * (rightCount + 1) * arr[index];}

最终优化

到这，先别撤，还没有完，这边可能有小伙伴运行代码后，发现耗时了80多毫秒才通过，感觉效率着实不行啊，这边其实和2点有比较大的关系了

• 使用了取模操作
• 使用了stack类

关于取模操作，我们可以变相的使用减法来替代，即如果值超过了1000000007，则将答案减去1000000007来防止溢出。

另外使用了stack类，其耗费的性能很高，stack类本来官方也不太推荐使用了，这边主要是stack类中有许多同步操作，导致了其性能下降，这边其实我们不太需要多线程同步处理，所以我们可以考虑换成ArrayDeque，这样能够大大提高效率。并且我们如果自己写一个数组来模拟单调栈也是很容易的，并且能够大大提高效率，代码如下：

public int sumSubarrayMins(int[] arr) {if (arr == null || arr.length == 0) {    return 0;}int n = arr.length;long ans = 0;long mod = 1000000007;// Stack stack = new Stack();int[] stack = new int[n];int top = -1;for(int i = 0; i < n; i++){    while(top >= 0 && arr[i] < arr[stack[top]]){ ans += count(stack, top, i) * arr[stack[top]]; if(ans >= mod){     ans -= mod; } --top;    }    stack[++top] = i;}while(top >= 0){    ans += count(stack, top, n)  * arr[stack[top]];    if(ans >= mod){ ans -= mod;    }    --top;}return (int) ans;}public long count(int[] stack, int top, int curLength){    int index = stack[top];    int leftIndex = top - 1 < 0 ? -1 : stack[top - 1];    int rightIndex = curLength;    int leftCount = index - leftIndex - 1;    int rightCount = rightIndex - index - 1;    return (long)(leftCount + 1) * (rightCount + 1);}

相信如果这道题的解题思路明白后，上面的代码也是很好理解了吧，我们自己维护了一个栈顶元素来实现和栈相同功能的一个数组，这样性能上又得到了相当的提高，那么，这样的算法你理解了吗？

最后还望各位兄弟姐妹们点个赞，关个注，更多的我理解的内容我还会陆续和大家分享的，谢谢大家！

郁金香导航