LeetCode 补充题 3. 求区间最小数乘区间和的最大值
题目描述
:::fold-green 相关原题
LeetCode 原题输入为正整数，答案对 1000000007 取模；本文允许元素为 0，返回不取模的最大得分。
:::
给定一个非负整数数组
nums。对于其中任意一个非空连续子数组，将该子数组的最小值乘以它的元素总和，得到这个子数组的得分。请返回所有非空连续子数组中的最大得分，无需返回对应区间，也不需要对结果取模。
示例 1：
输入：nums = [6,2,1]
输出：36
解释：选择子数组 [6]，得分为 6 × 6 = 36。
提示：
-
nums非空，且nums[i] >= 0。 - 最小值与元素总和必须取自同一个连续子数组。
- 前缀和与区间得分使用 64 位整数表示，计算结果需在该类型的可表示范围内。
题意分析
从数组中选一个非空连续区间，计算“区间内的最小值 × 区间内所有元素之和”，求能得到的最大乘积。这里区间和与最小值必须来自同一个区间。
原题数组允许零，以下按非负整数数组处理，并约定真实前缀和与乘积能由 64 位整数保存。非负性是扩张区间的依据：保持最小值不变时，加入更多元素不会减小区间和，乘积也不会减小。本题直接返回最大乘积，不要求取模。
解法：单调栈枚举最小值贡献 + 前缀和
核心思路
[!blue]
直接枚举左右端点会重复处理大量区间。换成枚举哪个元素充当最小值：固定
nums[j]后，只要向两侧扩张时不遇到更小的值，最小值就不会改变。由于数组元素均非负，扩张不会减小乘积，因此可以把允许区间扩到最大，而不是再枚举其中的短区间。先建立
prefix[i]，表示前i个元素之和。若可选区间是[left + 1, i - 1]，它的和便是prefix[i] - prefix[left + 1]，无需重新遍历。用栈保存下标，并让对应数值从栈底到栈顶严格递增。扫描到
i，只要当前值不大于栈顶，就弹出栈顶j。弹出后新的栈顶left是左侧最近的严格更小元素；当前i是右侧第一个小于或等于nums[j]的位置。两处边界都不纳入，计算中间区间和乘以nums[j]。右侧相等也弹出，会暂时让较早的相等元素算不到完整区间，但不会漏解。较右的相等元素随后入栈，它继承前面的更小左边界，能够覆盖之前同值元素经过的范围。于是一个区间中最小值若出现多次，最右的那次最终负责完整范围，前面的结算只是较短候选。
对任意最优区间，取其中最右的最小值位置。它按上述规则得到的区间至少覆盖原区间，且没有纳入更小值，因此乘积不会更差。这说明枚举这些栈结算区间足以覆盖最优答案。
扫描到数组末尾时仍可能有元素没有右边界，使用
i == n统一弹出，表示它们可以延伸到最后一项。虚拟下标只用于结算，不读取nums[n]，也不加入栈。
解题步骤
- 使用 64 位整数建立长度为
n + 1的前缀和。- 从左到右扫描，并维护数值严格递增的下标栈。
- 当前值不大于栈顶时弹出
j，取弹出后栈顶作为排除在区间外的左边界；空栈时左界为-1。- 计算
prefix[i] - prefix[left + 1]，乘以nums[j]更新最大值。- 当前真实下标入栈；到
i == n时只清栈，完成剩余区间结算。
代码实现
class Solution {
public long maxMinProduct(int[] nums) {
int n = nums.length;
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}
long ans = 0;
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i <= n; i++) {
// 当前不更大项确定右边界，相等项的完整归属交给更右位置
while (!stack.isEmpty() && (i == n || nums[stack.peek()] >= nums[i])) {
int j = stack.pop();
int left = stack.isEmpty() ? -1 : stack.peek();
// 弹出后的栈顶不属于区间，前缀差从它后一位开始
long sum = prefix[i] - prefix[left + 1];
ans = Math.max(ans, sum * nums[j]);
}
// 末尾仅负责清栈，不将虚拟位置加入候选
if (i < n) {
stack.push(i);
}
}
return ans;
}
}
func maxMinProduct(nums []int) int64 {
prefix := make([]int64, len(nums)+1)
for i, num := range nums {
prefix[i+1] = prefix[i] + int64(num)
}
var ans int64
stack := make([]int, 0, len(nums))
for i := 0; i <= len(nums); i++ {
// 当前不更大项确定右边界，相等项的完整归属交给更右位置
for len(stack) > 0 &&
(i == len(nums) || nums[stack[len(stack)-1]] >= nums[i]) {
j := stack[len(stack)-1]
stack = stack[:len(stack)-1]
left := -1
if len(stack) > 0 {
left = stack[len(stack)-1]
}
// 弹出后的栈顶不属于区间，前缀差从它后一位开始
product := (prefix[i] - prefix[left+1]) * int64(nums[j])
if product > ans {
ans = product
}
}
// 末尾仅负责清栈，不将虚拟位置加入候选
if i < len(nums) {
stack = append(stack, i)
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$。前缀和线性计算，每个真实下标至多入栈、出栈各一次，嵌套弹栈总次数仍为线性。
- 空间复杂度：$O(n)$，用于前缀和与下标栈。
关键点总结
[!green]
- 从枚举区间改为枚举最小值，非负条件使允许的最大区间成为最佳候选。
- 单调栈确定边界，前缀和计算边界之间的总和，两者职责不同。
- 相等元素由较右位置承担完整区间，既保持严格递增栈，也不会漏掉最优值。
- 末尾统一清栈，补齐没有真实右边界的候选。
易错点总结
[!yellow]
- 前缀差应减去
prefix[left + 1]，左边界本身是更小值，不能计入区间。- 右边界
i也不属于被弹项的本次区间，前缀右端使用prefix[i]。- 末尾不清栈会遗漏延伸到数组结尾的区间。
- 判断必须先处理
i == n，再访问当前元素，避免读取虚拟下标。- 该扩张理由依赖非负条件；含负数时区间变大不一定让乘积变好，不能直接照搬。
- 比较前取模会改变大小顺序；本实现按真实 64 位乘积直接比较和返回。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1856. 子数组最小乘积的最大值 | 中等 | 核心最小值乘区间和相同，原题最终取模；必须先比较真实乘积，不能用模值选最大。 |
| 84. 柱状图中最大的矩形 | 困难 | 同样固定最矮元素并找可扩展边界，本题权重是区间和，柱状图题权重是宽度。 |