Medium

题目描述

数组的 最小乘积 定义为这个数组的 最小值 乘以数组的 和。

  • 比如，数组 [3,2,5]（最小值是 2）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20

给你一个正整数数组 nums，返回 nums 任意 非空子数组 的 最小乘积 的 最大值。由于答案可能很大，返回答案对 10^9 + 7 取余 的结果。

请注意，最小乘积的最大值考虑的是取余操作 之前 的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64位有符号整数 来表示。

子数组 定义为一个数组的 连续 部分。

示例 1：

输入：nums = [1,2,3,2]
输出：14
解释：最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。
2 * (2+3+2) = 2 * 7 = 14

示例 2：

输入：nums = [2,3,3,1,2]
输出：18
解释：最小乘积的最大值由子数组 [3,3] （最小值是 3）得到。
3 * (3+3) = 3 * 6 = 18

示例 3：

输入：nums = [3,1,5,6,4,2]
输出：60
解释：最小乘积的最大值由子数组 [5,6,4] （最小值是 4）得到。
4 * (5+6+4) = 4 * 15 = 60

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^7

解题思路

解题思路

这道题的核心思想是以每个元素作为最小值来考虑问题。

基本思路： 对于数组中的每个元素 nums[i]，我们需要找到以 nums[i] 为最小值的最长子数组。这个子数组的范围是从左边第一个小于 nums[i] 的元素的下一位，到右边第一个小于 nums[i] 的元素的前一位。

算法步骤：

  1. 使用单调栈找边界：

    • 对于每个位置 i，找到其左边第一个小于 nums[i] 的位置 left[i]
    • 找到其右边第一个小于 nums[i] 的位置 right[i]
    • 以 nums[i] 为最小值的子数组范围就是 [left[i]+1, right[i]-1]

  2. 计算前缀和：

    • 预处理前缀和数组，便于快速计算任意子数组的和

  3. 计算最小乘积：

    • 对于每个位置 i，计算以 nums[i] 为最小值的子数组的最小乘积
    • 子数组和 = prefixSum[right[i]] - prefixSum[left[i]+1]
    • 最小乘积 = nums[i] * 子数组和

  4. 取最大值：

    • 遍历所有位置，取最小乘积的最大值

时间复杂度优化： 使用单调递增栈可以在 O(n) 时间内找到所有位置的左右边界，整体时间复杂度为 O(n)。

代码实现

class Solution {
public:
    int maxSumMinProduct(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        
        // 计算前缀和
        vector<long long> prefixSum(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        
        // 找左边界：左边第一个小于当前元素的位置
        vector<int> left(n, -1);
        stack<int> st;
        for (int i = 0; i < n; i++) {
            while (!st.empty() && nums[st.top()] >= nums[i]) {
                st.pop();
            }
            if (!st.empty()) {
                left[i] = st.top();
            }
            st.push(i);
        }
        
        // 找右边界：右边第一个小于当前元素的位置
        vector<int> right(n, n);
        while (!st.empty()) st.pop();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.empty() && nums[st.top()] >= nums[i]) {
                st.pop();
            }
            if (!st.empty()) {
                right[i] = st.top();
            }
            st.push(i);
        }
        
        long long maxProduct = 0;
        for (int i = 0; i < n; i++) {
            long long sum = prefixSum[right[i]] - prefixSum[left[i] + 1];
            maxProduct = max(maxProduct, (long long)nums[i] * sum);
        }
        
        return maxProduct % MOD;
    }
};

class Solution:
    def maxSumMinProduct(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        
        # 计算前缀和
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + nums[i]
        
        # 找左边界：左边第一个小于当前元素的位置
        left = [-1] * n
        stack = []
        for i in range(n):
            while stack and nums[stack[-1]] >= nums[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 nums[stack[-1]] >= nums[i]:
                stack.pop()
            if stack:
                right[i] = stack[-1]
            stack.append(i)
        
        max_product = 0
        for i in range(n):
            subarray_sum = prefix_sum[right[i]] - prefix_sum[left[i] + 1]
            max_product = max(max_product, nums[i] * subarray_sum)
        
        return max_product % MOD

public class Solution {
    public int MaxSumMinProduct(int[] nums) {
        const int MOD = 1000000007;
        int n = nums.Length;
        
        // 计算前缀和
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        
        // 找左边界：左边第一个小于当前元素的位置
        int[] left = new int[n];
        Stack<int> stack = new Stack<int>();
        for (int i = 0; i < n; i++) {
            left[i] = -1;
            while (stack.Count > 0 && nums[stack.Peek()] >= nums[i]) {
                stack.Pop();
            }
            if (stack.Count > 0) {
                left[i] = stack.Peek();
            }
            stack.Push(i);
        }
        
        // 找右边界：右边第一个小于当前元素的位置
        int[] right = new int[n];
        stack.Clear();
        for (int i = n - 1; i >= 0; i--) {
            right[i] = n;
            while (stack.Count > 0 && nums[stack.Peek()] >= nums[i]) {
                stack.Pop();
            }
            if (stack.Count > 0) {
                right[i] = stack.Peek();
            }
            stack.Push(i);
        }
        
        long maxProduct = 0;
        for (int i = 0; i < n; i++) {
            long sum = prefixSum[right[i]] - prefixSum[left[i] + 1];
            maxProduct = Math.Max(maxProduct, (long)nums[i] * sum);
        }
        
        return (int)(maxProduct % MOD);
    }
}

var maxSumMinProduct = function(nums) {
    const MOD = 1e9 + 7;
    const n = nums.length;
    
    // 计算前缀和
    const prefixSum = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + nums[i];
    }
    
    // 找左边界：左边第一个小于当前元素的位置
    const left = new Array(n).fill(-1);
    const stack = [];
    for (let i = 0; i < n; i++) {
        while (stack.length && nums[stack[stack.length - 1]] >= nums[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 && nums[stack[stack.length - 1]] >= nums[i]) {
            stack.pop();
        }
        if (stack.length) {
            right[i] = stack[stack.length - 1];
        }
        stack.push(i);
    }
    
    let maxProduct = 0;
    for (let i = 0; i < n; i++) {
        const sum = prefixSum[right[i]] - prefixSum[left[i] + 1];
        maxProduct = Math.max(maxProduct, nums[i] * sum);
    }
    
    return maxProduct % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)单调栈遍历数组一次，前缀和计算一次，最终遍历一次
空间复杂度O(n)需要额外的前缀和数组、左右边界数组和单调栈空间

相关题目