千问 LeetCode 2281.巫师的总力量和 public int totalStrength(int[] strength)

LeetCode 2281. 巫师的总力量和 是一道经典的 贡献法 + 单调栈 + 前缀和的前缀和 题目。题目要求对数组的所有非空连续子数组，计算：

min(subarray) * sum(subarray) 的总和，并对 10^9 + 7 取模。

✅ 解题思路（核心思想）

我们 不枚举所有子数组（那样是 O(n²)），而是 枚举每个元素作为最小值时的贡献。

步骤如下：

1. 使用单调栈 找出每个位置 i：
   - 左边第一个 严格小于 strength[i] 的位置 → left[i]
   - 右边第一个 小于等于 strength[i] 的位置 → right[i]

   > 这样可以确保每个子数组只被其 最左边的最小值 统计一次，避免重复。

2. 对于每个 i，它作为最小值能影响的区间是 [L, R] = [left[i]+1, right[i]-1]。

3. 在这个区间中，所有包含 i 的子数组的 元素和之和 可以通过 前缀和的前缀和 快速计算。

4. 最终贡献为：  
      strength[i] * (所有包含 i 且最小值为 strength[i] 的子数组的元素和之和)

✅ Java 实现（高效、清晰、取模安全）

import java.util.*;

public class Solution {
    public int totalStrength(int[] strength) {
        final long MOD = 1_000_000_007;
        int n = strength.length;

        // Step 1: 计算前缀和 s 和前缀和的前缀