Leetcode 周赛294

6077. 巫师的总力量和

题意描述：

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

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

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

请你返回 所有 巫师组的 总 力量之和。由于答案可能很大，请将答案对 109 + 7 取余 后返回。

子数组是一个数组里 非空 连续子序列。

思路：

参考03xf的博客

假设每个巫师当前就是最小的，向左向右扩展，最远能到达那个位置。这里可以用单调栈，找左边，右边第一个比自己小的位置。然后用前缀和，前缀和的前缀和对每一个区间求贡献。

class Solution {
public:
    int totalStrength(vector<int>& strength) {
        const int mod=1e9+7;
        int n=strength.size();
        vector<int> left(n,-1),right(n,n);
        //单调栈求左边小于当前数的第一个位置
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && strength[st.top()] >= strength[i])
                st.pop();
            if (!st.empty()) left[i] = st.top();
            st.push(i);
        }
        //单调栈求右边边小于当前数的第一个位置
        while(!st.empty()) st.pop();
        for(int i=n-1;i>=0;i--){//非空条件写在前面不容易出错
            while(!st.empty()&&strength[st.top()]>strength[i]) st.pop();
            if(!st.empty()) right[i]=st.top();
            st.push(i);
        }
        vector<int> s(n + 1), ss(n + 2);
        for (int i = 0; i < n; ++i) s[i + 1] = (s[i] + strength[i]) % mod; // 前缀和
        for (int i = 0; i <= n; ++i) ss[i + 1] = (ss[i] + s[i]) % mod;
        //枚举每一个巫师，假设当前就是最小，左边最远和右边最远。
        int ans=0;
        for(int i=0;i<n;i++){
            long  l=left[i]+1,r=right[i]-1;
            //求和
            long  sum=((i - l + 1) * (ss[r + 2] - ss[i + 1]) - (r - i + 1) * (ss[i + 1] - ss[l])) % mod;
            ans=(ans+sum*strength[i])%mod;
        }
        return (ans+mod)%mod;
    }
};