Hard

题目描述

作为一个王国的统治者，你拥有一支巫师军队。

给你一个下标从 0 开始的整数数组 strength ，其中 strength[i] 表示第 i 位巫师的力量值。对于连续的一组巫师（即巫师的力量值是 strength 的一个子数组），总力量定义为以下两个值的乘积：

  • 这组巫师中最弱巫师的力量值。
  • 这组中所有巫师的个人力量值之和。

返回所有连续巫师组的总力量之和。由于答案可能很大，请返回答案对 10^9 + 7 取余的结果。

子数组是数组中一个连续非空的元素序列。

示例 1：

输入：strength = [1,3,1,2]
输出：44
解释：以下是所有连续的巫师组：
- [1] 来自 [1,3,1,2]，总力量为 min([1]) * sum([1]) = 1 * 1 = 1
- [3] 来自 [1,3,1,2]，总力量为 min([3]) * sum([3]) = 3 * 3 = 9
- [1] 来自 [1,3,1,2]，总力量为 min([1]) * sum([1]) = 1 * 1 = 1
- [2] 来自 [1,3,1,2]，总力量为 min([2]) * sum([2]) = 2 * 2 = 4
- [1,3] 来自 [1,3,1,2]，总力量为 min([1,3]) * sum([1,3]) = 1 * 4 = 4
- [3,1] 来自 [1,3,1,2]，总力量为 min([3,1]) * sum([3,1]) = 1 * 4 = 4
- [1,2] 来自 [1,3,1,2]，总力量为 min([1,2]) * sum([1,2]) = 1 * 3 = 3
- [1,3,1] 来自 [1,3,1,2]，总力量为 min([1,3,1]) * sum([1,3,1]) = 1 * 5 = 5
- [3,1,2] 来自 [1,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

约束条件：

  • 1 <= strength.length <= 10^5
  • 1 <= strength[i] <= 10^9

解题思路

这是一道需要巧妙运用单调栈和前缀和的高难度题目。

核心思路： 直接枚举所有子数组会导致O(n³)的时间复杂度，无法通过。我们需要换个思路：考虑每个元素作为最小值时对答案的贡献。

算法步骤：

  1. 对于每个位置i，找到它作为最小值的所有子数组的范围。使用单调栈找到左边界（第一个小于strength[i]的位置）和右边界（第一个小于等于strength[i]的位置）。

  2. 关键优化：对于以位置i为最小值的所有子数组，我们需要高效计算它们的总和贡献。这里用到前缀和的前缀和技巧。

  3. 定义dp[i]为所有以位置i结尾的子数组的"和的总和"。通过递推关系可以快速计算：

    • dp[i] = dp[j] + (i-j) * prefixSum[i] 其中j是左边界。

  4. 最终答案是每个位置作为最小值时的贡献之和。

时间复杂度： O(n)，单调栈和前缀和处理都是线性时间。 空间复杂度： O(n)，需要额外的栈和数组空间。

代码实现

class Solution {
public:
    int totalStrength(vector<int>& strength) {
        const int MOD = 1e9 + 7;
        int n = strength.size();
        
        // 找到每个位置左边第一个更小的元素
        vector<int> left(n, -1);
        stack<int> stk;
        for (int i = 0; i < n; i++) {
            while (!stk.empty() && strength[stk.top()] >= strength[i]) {
                stk.pop();
            }
            if (!stk.empty()) left[i] = stk.top();
            stk.push(i);
        }
        
        // 找到每个位置右边第一个更小的元素
        vector<int> right(n, n);
        while (!stk.empty()) stk.pop();
        for (int i = n - 1; i >= 0; i--) {
            while (!stk.empty() && strength[stk.top()] > strength[i]) {
                stk.pop();
            }
            if (!stk.empty()) right[i] = stk.top();
            stk.push(i);
        }
        
        // 计算前缀和
        vector<long long> preSum(n + 1, 0);
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = (preSum[i] + strength[i]) % MOD;
        }
        
        // 计算前缀和的前缀和
        vector<long long> prePreSum(n + 2, 0);
        for (int i = 0; i <= n; i++) {
            prePreSum[i + 1] = (prePreSum[i] + preSum[i]) % MOD;
        }
        
        long long result = 0;
        for (int i = 0; i < n; i++) {
            int l = left[i], r = right[i];
            long long leftSum = ((long long)(i - l) * prePreSum[i + 1] - prePreSum[l + 1] + MOD) % MOD;
            long long rightSum = (prePreSum[r + 1] - prePreSum[i + 1] - (long long)(r - i) * prePreSum[i + 1] % MOD + MOD) % MOD;
            long long contribution = ((long long)strength[i] * (leftSum + rightSum)) % MOD;
            result = (result + contribution) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def totalStrength(self, strength: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(strength)
        
        # 找到每个位置左边第一个更小的元素
        left = [-1] * n
        stack = []
        for i in range(n):
            while stack and strength[stack[-1]] >= strength[i]:
                stack.pop()
            if stack:
                left[i] = stack[-1]
            stack.append(i)
        
        # 找到每个位置右边第一个更小的元素
        right = [n] * n
        stack = []
        for i in range(n-1, -1, -1):
            while stack and strength[stack[-1]] > strength[i]:
                stack.pop()
            if stack:
                right[i] = stack[-1]
            stack.append(i)
        
        # 计算前缀和
        pre_sum = [0] * (n + 1)
        for i in range(n):
            pre_sum[i + 1] = (pre_sum[i] + strength[i]) % MOD
        
        # 计算前缀和的前缀和
        pre_pre_sum = [0] * (n + 2)
        for i in range(n + 1):
            pre_pre_sum[i + 1] = (pre_pre_sum[i] + pre_sum[i]) % MOD
        
        result = 0
        for i in range(n):
            l, r = left[i], right[i]
            left_sum = ((i - l) * pre_pre_sum[i + 1] - pre_pre_sum[l + 1]) % MOD
            right_sum = (pre_pre_sum[r + 1] - pre_pre_sum[i + 1] - (r - i) * pre_pre_sum[i + 1]) % MOD
            contribution = (strength[i] * (left_sum + right_sum)) % MOD
            result = (result + contribution) % MOD
        
        return result

public class Solution {
    public int TotalStrength(int[] strength) {
        const int MOD = 1000000007;
        int n = strength.Length;
        
        // 找到每个位置左边第一个更小的元素
        int[] left = new int[n];
        Array.Fill(left, -1);
        Stack<int> stack = new Stack<int>();
        
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && strength[stack.Peek()] >= strength[i]) {
                stack.Pop();
            }
            if (stack.Count > 0) left[i] = stack.Peek();
            stack.Push(i);
        }
        
        // 找到每个位置右边第一个更小的元素
        int[] right = new int[n];
        Array.Fill(right, n);
        stack.Clear();
        
        for (int i = n - 1; i >= 0; i--) {
            while (stack.Count > 0 && strength[stack.Peek()] > strength[i]) {
                stack.Pop();
            }
            if (stack.Count > 0) right[i] = stack.Peek();
            stack.Push(i);
        }
        
        // 计算前缀和
        long[] preSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            preSum[i + 1] = (preSum[i] + strength[i]) % MOD;
        }
        
        // 计算前缀和的前缀和
        long[] prePreSum = new long[n + 2];
        for (int i = 0; i <= n; i++) {
            prePreSum[i + 1] = (prePreSum[i] + preSum[i]) % MOD;
        }
        
        long result = 0;
        for (int i = 0; i < n; i++) {
            int l = left[i], r = right[i];
            long leftSum = ((long)(i - l) * prePreSum[i + 1] - prePreSum[l + 1] + MOD) % MOD;
            long rightSum = (prePreSum[r + 1] - prePreSum[i + 1] - (long)(r - i) * prePreSum[i + 1] % MOD + MOD) % MOD;
            long contribution = ((long)strength[i] * (leftSum + rightSum)) % MOD;
            result = (result + contribution) % MOD;
        }
        
        return (int)result;
    }
}

var totalStrength = function(strength) {
    const MOD = 1e9 + 7;
    const n = strength.length;
    
    // 找到每个位置左边第一个更小的元素
    const left = new Array(n).fill(-1);
    const stack = [];
    
    for (let i = 0; i < n; i++) {
        while (stack.length && strength[stack[stack.length - 1]] >= strength[i]) {
            stack.pop();
        }
        if (stack.length) left[i] = stack[stack.length - 1];
        stack.push(i);
    }
    
    // 找到每个位置右边第一个更小的元素
    const right = new Array(n).fill(n);
    stack.length = 0;
    
    for (let i = n - 1; i >= 0; i--) {
        while (stack.length && strength[stack[stack.length - 1]] > strength[i]) {
            stack.pop();
        }
        if (stack.length) right[i] = stack[stack.length - 1];
        stack.push(i);
    }
    
    // 计算前缀和
    const preSum = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        preSum[i + 1] = (preSum[i] + strength[i]) % MOD;
    }
    
    // 计算前缀和的前缀和
    const prePreSum = new Array(n + 2).fill(0);
    for (let i = 0; i <= n; i++) {
        prePreSum[i + 1] = (prePreSum[i] + preSum[i]) % MOD;
    }
    
    let result = 0;
    for (let i = 0; i < n; i++) {
        const l = left[i], r = right[i];
        const leftSum = ((i - l) * prePreSum[i + 1] - prePreSum[l + 1] + MOD) % MOD;
        const rightSum = (prePreSum[r + 1] - prePreSum[i + 1] - (r - i) * prePreSum[i + 1] % MOD + MOD) % MOD;
        const contribution = (strength[i] * (leftSum + rightSum)) % MOD;
        result = (result + contribution) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
单调栈 + 前缀和O(n)O(n)

相关题目