跳至主要內容

LeetCode 1856. 子数组最小乘积的最大值——单调栈+前缀和组合

老张2026/4/30大约 7 分钟

LeetCode 1856. 子数组最小乘积的最大值——单调栈+前缀和组合

适读人群：Java 中高级工程师、备战大厂面试的同学 | 阅读时长：约22分钟 | 难度：中等

开篇故事

上一篇讲了贡献法求子数组最小值之和，这道 1856 是它的升级版——求「最小值 × 元素总和」的最大值。

初看题目，感觉和 907 差不多，无非是把统计「最小值出现了多少次」改成「以某元素为最小值时，子数组的元素总和是多少」。

前者只需要计数，后者需要快速求区间和——这自然就联想到了前缀和。单调栈确定每个元素的「支配区间」，前缀和快速计算区间总和，两者组合，把本来需要 O(n²) 的暴力，优化到了 O(n)。

这就是所谓「组合拳」：单一算法不够用时，把两个工具融合在一起。

一、题目解析

题目描述：

一个数组 arr 的最小乘积定义为该数组最小值与该数组的和的乘积。

给你一个正整数数组 nums，返回所有非空子数组的最小乘积中的最大值，结果对 10^9 + 7 取余。

示例：

输入：nums = [1,2,3,2]
输出：14
解释：所有非空子数组：
[1]->1*1=1, [2]->2*2=4, [3]->3*3=9, [2]->2*2=4
[1,2]->1*3=3, [2,3]->2*5=10, [3,2]->2*5=10
[1,2,3]->1*6=6, [2,3,2]->2*7=14
[1,2,3,2]->1*8=8
最大值：14

关键约束：

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

核心挑战： 枚举所有子数组是 O(n²)，对于每个子数组求最小值+求和又需要 O(n)，暴力是 O(n³)，必须优化。

二、解法一：暴力枚举

思路分析

枚举所有子数组的左右端点，动态维护最小值和总和。

class Solution {
    public int maxSumMinProduct(int[] nums) {
        final int MOD = 1_000_000_007;
        int n = nums.length;
        long maxProduct = 0;
        
        for (int i = 0; i < n; i++) {
            int minVal = nums[i];
            long sum = 0;
            for (int j = i; j < n; j++) {
                minVal = Math.min(minVal, nums[j]);
                sum += nums[j];
                maxProduct = Math.max(maxProduct, (long) minVal * sum);
            }
        }
        
        return (int) (maxProduct % MOD);
    }
}

复杂度分析

  • 时间复杂度：O(n²)。双重循环，内层每次更新最小值和和。
  • 空间复杂度：O(1)。

n=10^5 时，n²=10^10，必然超时。

三、解法二：单调栈确定边界 + 暴力区间求和

思路分析

先用单调栈预处理每个元素的「作为最小值的支配区间」，然后对每个区间暴力求和。

class Solution {
    public int maxSumMinProduct(int[] nums) {
        final int MOD = 1_000_000_007;
        int n = nums.length;
        
        // 找每个位置的左边第一个严格更小元素的下标（-1表示不存在）
        int[] leftSmaller = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            leftSmaller[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        
        // 找每个位置的右边第一个严格更小元素的下标（n表示不存在）
        int[] rightSmaller = new int[n];
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            rightSmaller[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }
        
        // 对每个元素，计算其支配区间的总和（暴力求和）
        long maxProduct = 0;
        for (int i = 0; i < n; i++) {
            int left = leftSmaller[i] + 1; // 区间左端点（包含）
            int right = rightSmaller[i] - 1; // 区间右端点（包含）
            long sum = 0;
            for (int j = left; j <= right; j++) {
                sum += nums[j];
            }
            maxProduct = Math.max(maxProduct, (long) nums[i] * sum);
        }
        
        return (int) (maxProduct % MOD);
    }
}

复杂度分析

  • 时间复杂度：O(n²)。虽然单调栈是 O(n)，但内层求和还是 O(n)，整体 O(n²)。
  • 空间复杂度：O(n)。

四、解法三（最优）：单调栈 + 前缀和

核心思想

在解法二基础上，用前缀和把区间求和从 O(n) 优化到 O(1)。

前缀和公式：

  • 设 prefix[i] = nums[0] + nums[1] + ... + nums[i-1]（前 i 个元素之和，prefix[0] = 0）
  • 区间 [left, right] 的总和 = prefix[right+1] - prefix[left]

完整代码

class Solution {
    public int maxSumMinProduct(int[] nums) {
        final int MOD = 1_000_000_007;
        int n = nums.length;
        
        // 前缀和（用 long 防止溢出，nums[i] 最大 10^7，n 最大 10^5，总和最大 10^12）
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        // 找左边第一个严格更小元素的下标
        int[] leftSmaller = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            leftSmaller[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        
        // 找右边第一个严格更小元素的下标
        int[] rightSmaller = new int[n];
        stack.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            rightSmaller[i] = stack.isEmpty() ? n : stack.peek();
            stack.push(i);
        }
        
        // 对每个元素计算最小乘积
        long maxProduct = 0;
        for (int i = 0; i < n; i++) {
            int left = leftSmaller[i] + 1;   // 包含的左端点
            int right = rightSmaller[i] - 1; // 包含的右端点
            
            // 区间 [left, right] 的总和 = prefix[right+1] - prefix[left]
            long rangeSum = prefix[right + 1] - prefix[left];
            
            // 最小乘积 = nums[i] × 区间总和
            long product = (long) nums[i] * rangeSum;
            maxProduct = Math.max(maxProduct, product);
        }
        
        // 取模后返回
        return (int) (maxProduct % MOD);
    }
}

手动模拟

以 nums = [1,2,3,2] 为例：

前缀和： prefix = [0, 1, 3, 6, 8]

左边更小元素下标（严格）：

  • i=0, nums[0]=1：无更小，leftSmaller[0]=-1
  • i=1, nums[1]=2：1<2，leftSmaller[1]=0
  • i=2, nums[2]=3：2<3，leftSmaller[2]=1
  • i=3, nums[3]=2：1<2，弹3，leftSmaller[3]=0

右边更小元素下标（严格）：

  • i=3, nums[3]=2：无更小，rightSmaller[3]=4
  • i=2, nums[2]=3：2<3，rightSmaller[2]=3
  • i=1, nums[1]=2：无更小，rightSmaller[1]=4
  • i=0, nums[0]=1：无更小，rightSmaller[0]=4

计算最小乘积：

inums[i]leftrightrangeSumproduct
0103prefix[4]-prefix[0]=88
1213prefix[4]-prefix[1]=714
2322prefix[3]-prefix[2]=39
3213prefix[4]-prefix[1]=714

最大值：14，正确！

复杂度分析

  • 时间复杂度：O(n)。前缀和 O(n)，两次单调栈各 O(n)，最终遍历 O(n)。
  • 空间复杂度：O(n)。前缀和数组和两个辅助数组。

五、举一反三

前缀和 + 单调栈 是一个经典组合，适用于所有「以某元素为最值的区间，快速求和/积」的场景：

题目思路
907. 子数组最小值之和单调栈贡献法（前一篇）
1856. 子数组最小乘积最大值本题
84. 柱状图最大矩形单调栈找左右边界，宽×高
85. 最大矩形（矩阵）逐行构造柱状图，调用84的方法

六、踩坑实录

坑一：前缀和数组长度要 n+1

前缀和的标准写法是 prefix[0]=0，prefix[i] = nums[0]+...+nums[i-1]，数组长度是 n+1。很多同学习惯性写成长度 n，导致越界或者查询公式写错。

long[] prefix = new long[n + 1]; // 长度 n+1，不是 n
prefix[0] = 0;
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}
// 区间[l, r]之和 = prefix[r+1] - prefix[l]

坑二：最大值是在最后取模，不能中途取模

这是很多人的误区：maxProduct 在计算过程中不能取模，因为取模后就无法比较大小了（(a % MOD) < (b % MOD) 不代表 a < b）。

必须用 long 存储真实的最大乘积，最后 maxProduct % MOD 才返回。

错误：

maxProduct = Math.max(maxProduct % MOD, product % MOD); // 错！

正确：

maxProduct = Math.max(maxProduct, product); // 比较真实值
// ...
return (int) (maxProduct % MOD); // 最后才取模

坑三：重复元素下左右边界的严格/非严格选择

这道题的元素可以有重复，比如 nums = [2,2]，如果左右都用「严格更小」，那两个 2 的支配区间都是整个数组，会重复计算；但由于是求最大值不是求和，重复计算不会影响正确性（两次取最大值结果相同）。

不过，从代码的一致性和理解的清晰度来说，左边严格、右边非严格是更规范的写法，这样每个子数组只被一个最小元素统计。本题求最大值，两种写法都正确，但要知道背后的原因。

七、总结

这道题把「单调栈确定边界」和「前缀和快速查询区间总和」两个经典技巧融合在一起，是学习算法组合应用的好例子。

核心步骤：

  1. 前缀和预处理，O(1) 查询任意区间和
  2. 单调栈预处理左右更小元素边界
  3. 对每个元素，计算以它为最小值的最大区间的最小乘积
  4. 全局取最大，最后取模

这个框架几乎是固定的，遇到类似题目可以直接套用，重点在于前缀和数组的边界处理和取模时机的把控。

编辑此页
最近更新:
贡献者: xiaozhangge