907. 子数组的最小值之和 : 常规「单调栈 + 数学」运用题

题目描述

这是 LeetCode 上的 ​​908. 最小差值 I​​ ，难度为 中等。

Tag : 「数学」、「单调栈」

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

由于答案可能很大，因此 返回答案模

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

提示：

单调栈 + 数学

原题解链接在 ​​这里​​，本次增加了更为详细的细节说明。

原问题为求所有子数组的最小值之和。

统计所有子数组需要枚举左右端点，复杂度为 ，对于每个子数组，我们还需要通过线性扫描的方式找到其最小值，复杂度为 ，因此朴素解法的整体复杂度为 ，题目给定数据范围为 ，会 ​​​TLE​​。

由于我们是从子数组中取最小值来进行累加，即参与答案构成的每个数必然某个具体的 。

因此我们可以将原问题转化为「考虑统计每个

对于某一个

我们可以想象以 为中心，分别往两端进行拓展，只要新拓展的边界不会改变「

换句话说，我们需要找到 作为最小值的最远左右边界，即找到 左右最近一个比其小的位置 ​​​l​​​ 和 ​​r​​。

在给定序列中，找到任意

到这里，我们会自然想到，通过单调栈的方式，分别预处理除 ​​l​​​ 和 ​​r​​ 数组：

• ​​l[i] = loc​​​ 含义为下标 ​​i​​​ 左边最近一个比 ​​arr[i]​​​ 小的位置是 ​​loc​​​（若在 左侧不存在比其小的数，则 ​​​loc = -1​​）
• ​​r[i] = loc​​​ 含义为下标 ​​i​​​ 右边最近一个比 ​​arr[i]​​​ 大的位置是 ​​loc​​​（若在 左侧不存在比其大的数，则 ​​​loc = n​​）

当我们预处理两数组后，通过简单「乘法原理」即可统计以

• 包含 的子数组左端点个数为
• 包含 的子数组右端点个数为

子数组的个数 子数组最小值 ，即是当前 对答案的贡献：。

统计所有 对答案的贡献即是最终答案，但我们忽略了「当 ​​arr​​ 存在重复元素，且该元素作为子数组最小值时，最远左右端点的边界越过重复元素时，导致重复统计子数组」的问题。

我们不失一般性的举个