题目形容
这是 LeetCode 上的 908. 最小差值 I,难度为 中等 。
Tag :「数学」、「枯燥栈」
给定一个整数数组 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
提醒:
- $1 <= arr.length <= 3 \times 10^4$
- $1 <= arr[i] <= 3 \times 10^4$
枯燥栈 + 数学
原题解链接在 这里,本次减少了更为具体的细节阐明。
原问题为求所有子数组的最小值之和。
统计所有子数组须要枚举左右端点,复杂度为 $O(n^2)$,对于每个子数组,咱们还须要通过线性扫描的形式找到其最小值,复杂度为 $O(n)$,因而奢侈解法的整体复杂度为 $O(n^3)$,题目给定数据范畴为 $3 \times 10^4$,会 TLE
。
因为咱们是从子数组中取最小值来进行累加,即参加答案形成的每个数必然某个具体的 $arr[i]$。
因而咱们能够将原问题转化为「思考统计每个 $arr[i]$ 对答案的奉献」。
对于某一个 $arr[i]$ 而言,咱们思考其可能作为哪些子数组的最小值。
咱们能够设想以 $arr[i]$ 为核心,别离往两端进行拓展,只有新拓展的边界不会扭转「$arr[i]$ 为以后子数组的最小值」的性质即可。
换句话说,咱们须要找到 $arr[i]$ 作为最小值的最远左右边界,即找到 $arr[i]$ 左右最近一个比其小的地位 l
和 r
。
在给定序列中,找到任意 $A[i]$ 最近一个比其大 / 小的地位,可应用「枯燥栈」进行求解。
到这里,咱们会天然想到,通过枯燥栈的形式,别离预处理除 l
和 r
数组:
l[i] = loc
含意为下标i
右边最近一个比arr[i]
小的地位是loc
(若在 $arr[i]$ 左侧不存在比其小的数,则loc = -1
)r[i] = loc
含意为下标i
左边最近一个比arr[i]
大的地位是loc
(若在 $arr[i]$ 左侧不存在比其大的数,则loc = n
)
当咱们预处理两数组后,通过简略「乘法原理」即可统计以 $arr[i]$ 为最小值时,子数组的个数:
- 蕴含 $arr[i]$ 的子数组左端点个数为 $a = i – l[i]$ 个
- 蕴含 $arr[i]$ 的子数组右端点个数为 $b = r[i] – i$ 个
子数组的个数 $\times$ 子数组最小值 $arr[i]$,即是以后 $arr[i]$ 对答案的奉献:$a \times b \times arr[i]$。
统计所有 $arr[i]$ 对答案的奉献即是最终答案,但咱们疏忽了「当 arr
存在反复元素,且该元素作为子数组最小值时,最远左右端点的边界越过反复元素时,导致反复统计子数组」的问题。
咱们不失一般性的举个 🌰 来了解(下图):
为了打消这种反复统计,咱们能够将「最远左右边界」的一端,从「严格小于」调整为「小于等于」,从而实现半开半闭的成果。
Java 代码:
class Solution {int MOD = (int)1e9+7;
public int sumSubarrayMins(int[] arr) {
int n = arr.length, ans = 0;
int[] l = new int[n], r = new int[n];
Arrays.fill(l, -1); Arrays.fill(r, n);
Deque<Integer> d = new ArrayDeque<>();
for (int i = 0; i < n; i++) {while (!d.isEmpty() && arr[d.peekLast()] >= arr[i]) r[d.pollLast()] = i;
d.addLast(i);
}
d.clear();
for (int i = n - 1; i >= 0; i--) {while (!d.isEmpty() && arr[d.peekLast()] > arr[i]) l[d.pollLast()] = i;
d.addLast(i);
}
for (int i = 0; i < n; i++) {int a = i - l[i], b = r[i] - i;
ans += a * 1L * b % MOD * arr[i] % MOD;
ans %= MOD;
}
return ans;
}
}
TypeScript 代码:
const MOD = 1000000007
function sumSubarrayMins(arr: number[]): number {
let n = arr.length, ans = 0
const l = new Array<number>(n).fill(-1), r = new Array<number>(n).fill(n)
const stk = new Array<number>(n).fill(0)
let he = 0, ta = 0
for (let i = 0; i < n; i++) {while (he < ta && arr[stk[ta - 1]] >= arr[i]) r[stk[--ta]] = i
stk[ta++] = i
}
he = ta = 0
for (let i = n - 1; i >= 0; i--) {while (he < ta && arr[stk[ta - 1]] > arr[i]) l[stk[--ta]] = i
stk[ta++] = i
}
for (let i = 0; i < n; i++) {const a = i - l[i], b = r[i] - i
ans += a * b % MOD * arr[i] % MOD
ans %= MOD
}
return ans
}
Python 代码:
class Solution:
def sumSubarrayMins(self, arr: List[int]) -> int:
n, ans = len(arr), 0
l, r = [-1] * n, [n] * n
stk = []
for i in range(n):
while stk and arr[stk[-1]] >= arr[i]:
r[stk.pop()] = i
stk.append(i)
stk = []
for i in range(n - 1, -1, -1):
while stk and arr[stk[-1]] > arr[i]:
l[stk.pop()] = i
stk.append(i)
for i in range(n):
a, b = i - l[i], r[i] - i
ans += a * b * arr[i]
return ans % (10 ** 9 + 7)
- 工夫复杂度:$O(n)$
- 空间复杂度:$O(n)$
优化
实际上,当咱们从栈中弹出某个 $arr[cur]$ 时,其右边界必然是导致其弹出的 arr[r]
(以后所遍历到的元素),而 $arr[cur]$ 若存在左边界,必然是位于 $cur$ 栈中的前一地位,即 $arr[cur]$ 弹出后的新栈顶元素(若不存在物理左边界,则左边界为 $-1$)。
Java 代码:
class Solution {int MOD = (int)1e9+7;
public int sumSubarrayMins(int[] arr) {
int n = arr.length, ans = 0;
Deque<Integer> d = new ArrayDeque<>();
for (int r = 0; r <= n; r++) {int t = r < n ? arr[r] : 0;
while (!d.isEmpty() && arr[d.peekLast()] >= t) {int cur = d.pollLast();
int l = d.isEmpty() ? -1 : d.peekLast();
int a = cur - l, b = r - cur;
ans += a * 1L * b % MOD * arr[cur] % MOD;
ans %= MOD;
}
d.addLast(r);
}
return ans;
}
}
TypeScript 代码:
const MOD = 1000000007
function sumSubarrayMins(arr: number[]): number {
let n = arr.length, ans = 0
const stk = new Array<number>(n).fill(0)
let he = 0, ta = 0
for (let r = 0; r <= n; r++) {const t = r < n ? arr[r] : 0
while (he < ta && arr[stk[ta - 1]] >= t) {const cur = stk[--ta]
const l = he < ta ? stk[ta - 1] : -1
const a = cur - l, b = r - cur
ans += a * b % MOD * arr[cur] % MOD
ans %= MOD
}
stk[ta++] = r
}
return ans
}
Python 代码:
class Solution:
def sumSubarrayMins(self, arr: List[int]) -> int:
n, ans = len(arr), 0
stk = []
for r in range(n + 1):
t = arr[r] if r < n else 0
while stk and arr[stk[-1]] >= t:
cur = stk.pop()
l = stk[-1] if stk else -1
a, b = cur - l, r - cur
ans += a * b * arr[cur]
stk.append(r)
return ans % (10 ** 9 + 7)
- 工夫复杂度:$O(n)$
- 空间复杂度:$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.907
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。
在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。
在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布