Description

给定一个长度为\(n\)的数组\(a\),求该数组中所有子数组的最小值之和。

Constraints

  • \(1 \le n \le 3 \cdot 10^4\)
  • \(1 \le a_i \le 3 \cdot 10^4\)

Solution

假设你知道每个最小值\(a_i = min\_v\)所覆盖的区间范围\([lo, hi]\),那么可以通过组合数得知子答案:\(sub\_ans_i = (i - lo + 1) * (hi - i + 1) * min\_v\)。

然后通过子答案之和就可以得到答案:\(ans = \sum_{i=0}^{n} sub\_ans_i\)。

而最小值的覆盖范围可以通过单调栈得出。

Code

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        long ans = 0;
        constexpr long MOD = 1e9 + 7;
        // {leftmost, min_index, min_v}
        stack<tuple<size_t, size_t, int>> stk;
        auto cal = [MOD](size_t l, size_t i, size_t r, int v) {
            long llen = i - l + 1;
            long rlen = r - i + 1;
            return llen * rlen * v % MOD;
        };
        for(size_t i = 0; i < arr.size(); ++i) {
            auto v = arr[i];
            auto leftmost = i;
            while(!stk.empty() && v < get<2>(stk.top())) {
                auto [tleft, tidx, tv] = stk.top();
                stk.pop();
                ans += cal(tleft, tidx, i-1, tv);
                ans %= MOD;
                leftmost = tleft;
            }
            stk.emplace(leftmost, i, v);
        }
        while(!stk.empty()) {
            auto [l, i, v] = stk.top();
            stk.pop();
            ans += cal(l, i, arr.size()-1, v);
            ans %= MOD;
        }
        return ans;
    }
};

LeetCode-907 Sum of Subarray Minimums