# 2281.sum-of-total-strength-of-wizards

### 题目地址(2281. 巫师的总力量和)

<https://leetcode.cn/problems/sum-of-total-strength-of-wizards/>

### 题目描述

```
作为国王的统治者，你有一支巫师军队听你指挥。

给你一个下标从 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 <= 105
1 <= strength[i] <= 109
```

### 前置知识

*

### 公司

* 暂无

### 思路

如果想做出来这道题，建议先做一下简化版的这道题：[907. 子数组的最小值之和](https://leetcode.cn/problems/sum-of-subarray-minimums/)

简单说一下上面那个简化版的题目。

一种思考方式是**计算每一个数组项 nums\[i]** 对结果的贡献 c\[i]，那么答案就是对 c\[i] 求和。

nums\[i] 对结果的贡献是包含 nums\[i] 的子数组，且该子数组的最小值是 nums\[i]。于是，我们可以分别找到 nums\[i] 左侧和右侧第一个比 nums\[i] 小的值 l 和 r，那么子数组 \[L,R] 就是一个符合要求的子数组。其中 L 范围是 \[l+1,i] R 范围是 \[i,r-1]。

根据笛卡尔积可知，每一项 a 对结果的贡献就是 `a * (i - l) * (r - i)`

而找到左侧（或者右侧）第一个比其大（或者小）的元素考虑使用单调栈。

参考代码：

```py
class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        n = len(A)
        st = []
        left = [-1] * n
        right = [n] * n
        res = 0
        for i, a in enumerate(A):
            while st and a <= A[st[-1]]:
                right[st.pop()] = i
            if st:
                left[i] = st[-1]
            st.append(i)
        for i, a in enumerate(A):
            res += a * (i - left[i]) * (right[i] - i)

        return res % 1000000007

```

对这道题来说，我们也需要知道左侧和右侧第一个比其小的，因此使用单调栈也可以解决。不同的是，我们需要求所有子数组和的和。

和前面一样子数组 \[L,R] 就是一个符合要求的子数组。其中 L 范围是 \[l+1,i] R 范围是 \[i,r-1]。

关键是每一项 a 对结果的贡献是多少呢？我们知道子数组和可以用前缀和来计算，只要知道左右端点即可求出。而这里有两个变量，一个是左边界，一个是右边界。

假设我们符合要求的子数组是 `l1,l2,l3,a,r1,r2,r3`不妨固定其中一个，以固定左边界为例。我们先固定 l1， 那么右边界就可以是 r1，r2,r3。此时的贡献是 s\[r3] - s\[l1]（即子 l1 到 r3 这一段的贡献）+ s\[r2] - s\[l1]（即子 l1 到 r2 这一段的贡献）+ s\[r1] - s\[l1]（即子 l1 到 r1 这一段的贡献）。类似的，我们需要固定 l2 和 l3 。 因此一共有 3 个 s\[l1]，3 就是 a 右侧元素个数 rn。

因此`每一项 a 对结果的贡献就是 a * (racc * ln - lacc * rn) % mod`

### 关键点

* 计算每一项对结果的贡献
* 固定一个变量

### 代码

* 语言支持：Python3

Python3 Code:

```python

class Solution:
    def totalStrength(self, A):
        mod = 10 ** 9 + 7
        n = len(A)

        right = [n] * n
        left = [-1] * n
        st = []
        for i in range(n):
            while st and A[st[-1]] >= A[i]:
                right[st.pop()] = i
            if st:
                left[i] = st[-1]
            st.append(i)

        res = 0
        acc = list(accumulate(accumulate(A), initial = 0))
        for i in range(n):
            l, r = left[i], right[i]
            lacc = acc[i] - acc[max(l, 0)]
            racc = acc[r] - acc[i]
            ln, rn = i - l, r - i
            res += A[i] * (racc * ln - lacc * rn) % mod
        return res % mod

```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度：$O(n)$
* 空间复杂度：$O(n)$

### 参考

* [lee: Python Solution, O(n)](https://leetcode.com/problems/sum-of-total-strength-of-wizards/discuss/2061985/Python-Solution-O\(n\))

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/6jaza9.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/2281.sum-of-total-strength-of-wizards.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.