题目描述
leetcode Hard
作为国王的统治者，你有一支巫师军队听你指挥。
给你一个下标从 0 开始的整数数组 strength ，其中 strength[i] 表示第 i 位巫师的力量值。对于连续的一组巫师（也就是这些巫师的力量值是 strength 的 子数组），总力量 定义为以下两个值的 乘积 ：
巫师中 最弱 的能力值。
组中所有巫师的个人力量值 之和 。
请你返回 所有 巫师组的 总 力量之和。由于答案可能很大，请将答案对 109 + 7 取余 后返回。
子数组 是一个数组里 非空 连续子序列。
示例1：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 输入：strength =
输出：44
解释：以下是所有连续巫师组：
- 中 ，总力量值为 min() * sum() = 1 * 1 = 1
- 中 ，总力量值为 min() * sum() = 3 * 3 = 9
- 中 ，总力量值为 min() * sum() = 1 * 1 = 1
- 中 ，总力量值为 min() * sum() = 2 * 2 = 4
- 中 ，总力量值为 min() * sum() = 1 * 4 = 4
- 中 ，总力量值为 min() * sum() = 1 * 4 = 4
- 中 ，总力量值为 min() * sum() = 1 * 3 = 3
- 中 ，总力量值为 min() * sum() = 1 * 5 = 5
- 中 ，总力量值为 min() * sum() = 1 * 6 = 6
- 中 ，总力量值为 min() * sum() = 1 * 7 = 7
所有力量值之和为 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44 。
|
提示1：
1
2
| 1 <= strength.length <= 10^5
1 <= strength[i] <= 10^9
|
每个元素对答案的贡献
思路是考虑每个元素作为最小值时对答案做出的贡献为多少。
设当前遍历下标为 $idx$ ， 那么以 $strength[idx]$ 作为子数组的最小值时，子数组左右侧最远能去到第一个更小元素处，由于 $strength$ 存在重复元素，为了避免重复计算，我们可以让边界为左闭右开，如果设 $left[idx]$ 为左侧第一个小于等于当前元素的下标，$right[idx]$ 为右侧第一个小于当前元素的下标，那么左边界就为 $left[idx] + 1$ ，右边界为 $right[idx] - 1$，而对于 $left$ 和 $right$ ，可以通过单调栈 $O(N)$ 的预处理出来。
剩余问题为求出这些子数组的和，设 $left[i] + 1$ 为 $L$ ，$right[i] - 1$ 为 $R$ ，前缀和数组为 $S$，子数组的左端点为 $i$ ，右端点为 $j$ ，如果先固定子数组的右端点，此时子数组的和为：
$$
\begin{align}
&\sum_{j = idx}^{R}(S_{idx} - S_{L - 1} + S_{idx} - S_{L} + … + S_{idx} - S_{idx - 1})\\
= & \sum_{j = idx}^{R}(\sum_{i = L - 1}^{idx - 1}(S_j - S_i))\\
= & \sum_{j = idx}^{R}((idx - L + 1) * S_j - \sum_{i = L - 1}^{idx - 1}S_i)\\
= & \sum_{j = idx}^{R}((idx - L + 1) * S_j ) - \sum_{j = idx}^{R}\sum_{i = L - 1}^{idx - 1}S_i\\
= & (idx - L + 1)\sum_{j = idx}^{R} S_j - (R - idx + 1)\sum_{i = L - 1}^{idx - 1}S_i\\
\end{align}
$$
而上式中的 $\sum S_i$ 可以通过预处理前缀和的前缀和来得出
总体时间复杂度为 $O(N)$ 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
private static final int MOD = (int) (1e9 + 7);
public int totalStrength(int[] strength) {
int n = strength.length;
int[] left = new int[n];
int[] right = new int[n];
long[] preSumSum = new long[n + 1];
long preSum = 0;
Deque<Integer> monoStack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
preSum += strength[i];
preSumSum[i + 1] = (preSumSum[i] + preSum) % MOD;
while (!monoStack.isEmpty() && strength[monoStack.peek()] > strength[i]) {
right[monoStack.pop()] = i;
}
left[i] = monoStack.isEmpty() ? -1 : monoStack.peek();
monoStack.push(i);
}
while (!monoStack.isEmpty()) {
right[monoStack.pop()] = n;
}
long ans = 0;
for (int idx = 0; idx < n; idx++) {
int L = left[idx] + 1;
int R = right[idx] - 1;
long preL = L == 0 ? 0 : preSumSum[L - 1];
long sum = ((((idx - L + 1) * (((preSumSum[R + 1] - preSumSum[idx]) + MOD) % MOD))) % MOD - (((R - idx + 1) * (((preSumSum[idx] - preL) + MOD) % MOD)) % MOD) + MOD) % MOD;
ans = (ans + ((sum * strength[idx]) % MOD)) % MOD;
}
return ((int) ans);
}
}
|