907.子数组的最小值之和

链接：907.子数组的最小值之和
难度：Medium
标签：栈、数组、动态规划、单调栈
简介：给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

题解 1 - cpp

• 编辑时间：2022-10-28
• 执行用时：104ms
• 内存消耗：41.3MB
• 编程语言：cpp
• 解法介绍：单调栈，统计每个点第一个左边大的数，和第二个右边大的数，统计左边数量+右边数量+左右交叉数量。

class Solution {
public:
    const int mod = 1e9 + 7;
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        long long ans = 0;
        vector<int> l(n, -1), r(n, n);
        stack<int> s;
        for (int i = 0; i < n; i++) {
            while (s.size() && arr[s.top()] > arr[i]) r[s.top()] = i, s.pop();
            if (s.size()) l[i] = s.top();
            s.push(i);
        }
        for (int i = 0; i < n; i++) {
            int left = i - l[i] - 1, right = r[i] - i - 1;
            ans = (ans +(static_cast<long long>(left) + right + left * right + 1) * arr[i]) % mod;
        }
        return ans;
    }
};

题解 2 - python

• 编辑时间：2023-11-27
• 执行用时：140ms
• 内存消耗：20.25MB
• 编程语言：python
• 解法介绍：单调栈，找出当前点为最小值时的区间。

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        n = len(arr)
        prev = [-1] * n
        next = [n] * n
        s = []
        ans = 0
        for i in range(n):
            while s and arr[s[-1]] >= arr[i]:
                next[s[-1]] = i
                s.pop()
            if s: prev[i] = s[-1]
            s.append(i)
        return sum((next[i] - i) * (i - prev[i]) * arr[i] for i in range(n)) % (10** 9 + 7)