LeetCode 题解工作台
巫师的总力量和
作为国王的统治者，你有一支巫师军队听你指挥。 给你一个下标从 0 开始的整数数组 strength ，其中 strength[i] 表示第 i 位巫师的力量值。对于连续的一组巫师（也就是这些巫师的力量值是 strength 的 子数组 ）， 总力量 定义为以下两个值的 乘积 ： 巫师中 最弱 的能力…
4
题型
4
代码语言
3
相关题
当前训练重点
困难 · 栈·状态
答案摘要
相似题目： - [907. 子数组的最小值之和](https://github.com/doocs/leetcode/blob/main/solution/0900-0999/0907.Sum%20of%20Subarray%20Minimums/README.md)
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
作为国王的统治者，你有一支巫师军队听你指挥。
给你一个下标从 0 开始的整数数组 strength ，其中 strength[i] 表示第 i 位巫师的力量值。对于连续的一组巫师（也就是这些巫师的力量值是 strength 的 子数组），总力量 定义为以下两个值的 乘积 ：
- 巫师中 最弱 的能力值。
- 组中所有巫师的个人力量值 之和 。
请你返回 所有 巫师组的 总 力量之和。由于答案可能很大，请将答案对 109 + 7 取余 后返回。
子数组 是一个数组里 非空 连续子序列。
示例 1：
输入：strength = [1,3,1,2] 输出：44 解释：以下是所有连续巫师组： - [1,3,1,2] 中 [1] ，总力量值为 min([1]) * sum([1]) = 1 * 1 = 1 - [1,3,1,2] 中 [3] ，总力量值为 min([3]) * sum([3]) = 3 * 3 = 9 - [1,3,1,2] 中 [1] ，总力量值为 min([1]) * sum([1]) = 1 * 1 = 1 - [1,3,1,2] 中 [2] ，总力量值为 min([2]) * sum([2]) = 2 * 2 = 4 - [1,3,1,2] 中 [1,3] ，总力量值为 min([1,3]) * sum([1,3]) = 1 * 4 = 4 - [1,3,1,2] 中 [3,1] ，总力量值为 min([3,1]) * sum([3,1]) = 1 * 4 = 4 - [1,3,1,2] 中 [1,2] ，总力量值为 min([1,2]) * sum([1,2]) = 1 * 3 = 3 - [1,3,1,2] 中 [1,3,1] ，总力量值为 min([1,3,1]) * sum([1,3,1]) = 1 * 5 = 5 - [1,3,1,2] 中 [3,1,2] ，总力量值为 min([3,1,2]) * sum([3,1,2]) = 1 * 6 = 6 - [1,3,1,2] 中 [1,3,1,2] ，总力量值为 min([1,3,1,2]) * sum([1,3,1,2]) = 1 * 7 = 7 所有力量值之和为 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44 。
示例 2：
输入：strength = [5,4,6] 输出：213 解释：以下是所有连续巫师组： - [5,4,6] 中 [5] ，总力量值为 min([5]) * sum([5]) = 5 * 5 = 25 - [5,4,6] 中 [4] ，总力量值为 min([4]) * sum([4]) = 4 * 4 = 16 - [5,4,6] 中 [6] ，总力量值为 min([6]) * sum([6]) = 6 * 6 = 36 - [5,4,6] 中 [5,4] ，总力量值为 min([5,4]) * sum([5,4]) = 4 * 9 = 36 - [5,4,6] 中 [4,6] ，总力量值为 min([4,6]) * sum([4,6]) = 4 * 10 = 40 - [5,4,6] 中 [5,4,6] ，总力量值为 min([5,4,6]) * sum([5,4,6]) = 4 * 15 = 60 所有力量值之和为 25 + 16 + 36 + 36 + 40 + 60 = 213 。
提示：
1 <= strength.length <= 1051 <= strength[i] <= 109
解题思路
class Solution:
def totalStrength(self, strength: List[int]) -> int:
n = len(strength)
left = [-1] * n
right = [n] * n
stk = []
for i, v in enumerate(strength):
while stk and strength[stk[-1]] >= v:
stk.pop()
if stk:
left[i] = stk[-1]
stk.append(i)
stk = []
for i in range(n - 1, -1, -1):
while stk and strength[stk[-1]] > strength[i]:
stk.pop()
if stk:
right[i] = stk[-1]
stk.append(i)
ss = list(accumulate(list(accumulate(strength, initial=0)), initial=0))
mod = int(1e9) + 7
ans = 0
for i, v in enumerate(strength):
l, r = left[i] + 1, right[i] - 1
a = (ss[r + 2] - ss[i + 1]) * (i - l + 1)
b = (ss[i + 1] - ss[l]) * (r - i + 1)
ans = (ans + (a - b) * v) % mod
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ability to manage large inputs efficiently without brute force methods.
- question_mark
Understanding of monotonic stacks and their application in reducing time complexity.
- question_mark
Skill in handling large numbers and applying modulo operations to ensure correctness.
常见陷阱
外企场景- error
Not using a monotonic stack to reduce redundant calculations for subarrays.
- error
Forgetting to apply modulo 10^9 + 7 during the summation process, causing overflow or incorrect results.
- error
Relying on brute-force methods to calculate all subarrays, which can be too slow for large inputs.
进阶变体
外企场景- arrow_right_alt
Optimizing for larger inputs by reducing time complexity with better state management.
- arrow_right_alt
Adjusting the solution to handle varying constraints, such as different ranges for wizard strengths.
- arrow_right_alt
Exploring variations of the problem where other properties, like sum or product, need to be calculated instead of total strength.