Medium

题目描述

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，返回答案对 10^9 + 7 取余的结果。

示例 1：

输入：arr = [3,1,2,4]
输出：17
解释：
子数组为 [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]。
最小值为 3, 1, 2, 4, 1, 1, 2, 1, 1, 1。
总和为 17。

示例 2：

输入：arr = [11,81,94,43,3]
输出：444

提示：

  • 1 <= arr.length <= 3 * 10^4
  • 1 <= arr[i] <= 3 * 10^4

解题思路

这道题需要计算所有子数组的最小值之和。暴力解法是枚举所有子数组，时间复杂度为 O(n³)，会超时。

核心思路：对于每个元素 arr[i]，计算它作为最小值的子数组数量，然后乘以 arr[i] 得到贡献值。

关键在于找到每个元素的「影响范围」：

  • 左边界：找到左侧第一个小于当前元素的位置
  • 右边界：找到右侧第一个小于等于当前元素的位置

使用单调递增栈来高效求解：

  1. 遍历数组，维护单调递增栈
  2. 当遇到更小元素时，栈顶元素找到了右边界
  3. 栈中下一个元素就是左边界
  4. 计算贡献：arr[i] * (i - left) * (right - i)

注意事项：

  • 为避免重复计算，左边界用"严格小于"，右边界用"小于等于"
  • 需要处理边界情况（栈为空时的边界）
  • 结果要对 10^9 + 7 取余

这种方法时间复杂度为 O(n)，空间复杂度为 O(n)，是最优解法。

代码实现

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        int n = arr.size();
        vector<int> left(n), right(n);
        stack<int> st;
        
        // 计算左边界：左侧第一个小于当前元素的位置
        for (int i = 0; i < n; i++) {
            while (!st.empty() && arr[st.top()] >= arr[i]) {
                st.pop();
            }
            left[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }
        
        // 清空栈，计算右边界：右侧第一个小于等于当前元素的位置
        while (!st.empty()) st.pop();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && arr[st.top()] > arr[i]) {
                st.pop();
            }
            right[i] = st.empty() ? n : st.top();
            st.push(i);
        }
        
        long long result = 0;
        for (int i = 0; i < n; i++) {
            long long contribution = (long long)arr[i] * (i - left[i]) * (right[i] - i);
            result = (result + contribution) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(arr)
        left = [0] * n
        right = [0] * n
        stack = []
        
        # 计算左边界：左侧第一个小于当前元素的位置
        for i in range(n):
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()
            left[i] = -1 if not stack else stack[-1]
            stack.append(i)
        
        # 清空栈，计算右边界：右侧第一个小于等于当前元素的位置
        stack.clear()
        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()
            right[i] = n if not stack else stack[-1]
            stack.append(i)
        
        result = 0
        for i in range(n):
            contribution = arr[i] * (i - left[i]) * (right[i] - i)
            result = (result + contribution) % MOD
        
        return result

public class Solution {
    public int SumSubarrayMins(int[] arr) {
        const int MOD = 1000000007;
        int n = arr.Length;
        int[] left = new int[n];
        int[] right = new int[n];
        Stack<int> stack = new Stack<int>();
        
        // 计算左边界：左侧第一个小于当前元素的位置
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && arr[stack.Peek()] >= arr[i]) {
                stack.Pop();
            }
            left[i] = stack.Count == 0 ? -1 : stack.Peek();
            stack.Push(i);
        }
        
        // 清空栈，计算右边界：右侧第一个小于等于当前元素的位置
        stack.Clear();
        for (int i = n - 1; i >= 0; i--) {
            while (stack.Count > 0 && arr[stack.Peek()] > arr[i]) {
                stack.Pop();
            }
            right[i] = stack.Count == 0 ? n : stack.Peek();
            stack.Push(i);
        }
        
        long result = 0;
        for (int i = 0; i < n; i++) {
            long contribution = (long)arr[i] * (i - left[i]) * (right[i] - i);
            result = (result + contribution) % MOD;
        }
        
        return (int)result;
    }
}

var sumSubarrayMins = function(arr) {
    const MOD = 1e9 + 7;
    const n = arr.length;
    
    // Find previous less element for each index
    const prevLess = new Array(n).fill(-1);
    const stack1 = [];
    for (let i = 0; i < n; i++) {
        while (stack1.length && arr[stack1[stack1.length - 1]] > arr[i]) {
            stack1.pop();
        }
        if (stack1.length) {
            prevLess[i] = stack1[stack1.length - 1];
        }
        stack1.push(i);
    }
    
    // Find next less or equal element for each index
    const nextLessEqual = new Array(n).fill(n);
    const stack2 = [];
    for (let i = n - 1; i >= 0; i--) {
        while (stack2.length && arr[stack2[stack2.length - 1]] >= arr[i]) {
            stack2.pop();
        }
        if (stack2.length) {
            nextLessEqual[i] = stack2[stack2.length - 1];
        }
        stack2.push(i);
    }
    
    let result = 0;
    for (let i = 0; i < n; i++) {
        const left = i - prevLess[i];
        const right = nextLessEqual[i] - i;
        result = (result + arr[i] * left * right) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)每个元素最多进栈出栈一次，总体为线性时间
空间复杂度O(n)需要额外的数组存储左右边界和栈空间

相关题目