题目描述
这是 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
存在重复元素,且该元素作为子数组最小值时,最远左右端点的边界越过重复元素时,导致重复统计子数组」的问题。
我们不失一般性的举个
标签:arr,907,int,stk,最小值,ans,MOD,单调,ta From: https://blog.51cto.com/acoier/5806593