LeetCode 补充题 3. 求区间最小数乘区间和的最大值

2023-11-01 HGNULB 约 6 分钟

文章信息 8 个分类 2 个标签

分类

题目描述

✅ 补充题 3. 求区间最小数乘区间和的最大值

题意分析

给定一个由正整数组成的数组，在它的全部非空连续子数组中，每个子数组都能算出两个量：里面的最小元素、以及所有元素之和。把这两个量相乘得到该子数组的得分，问所有子数组里最高的得分是多少。

「连续」是核心约束，意味着候选对象由左右两个端点唯一确定，一共 $\frac{n(n+1)}{2}$ 个。元素全为正是另一条关键信号：它保证子数组一旦向外扩张，和就严格变大，绝不会因为扩进负数而变小。这条性质后面会被反复用到，一旦允许出现负数或零，整个推理都要重来。

边界方面，单个元素也算合法子数组，此时得分是它自己的平方；数组中存在大量相等元素时，「谁是最小值」会出现归属歧义，必须定一套规则避免同一个区间被算多遍或一次都不算。数值上，和与最小值相乘的规模远超 32 位，必须用 64 位整数。

解法：单调栈枚举最小值贡献 + 前缀和

核心思路

暴力枚举所有连续区间需要 $O(n^2)$。更合适的枚举方式是：固定下标 i，让 nums[i] 作为区间最小值，再求它能贡献的最高得分。

对重复最小值采用不对称边界：右侧遇到第一个小于等于 nums[i] 的元素时结算，左侧边界取第一个严格小于它的元素。这样较早的相等元素在右侧截断，最右侧的相等元素负责覆盖完整区间。由于数组元素均为正，在最小值不变时区间扩得越大、区间和越大，因此只需计算该边界内的最大区间。区间和用前缀和 $O(1)$ 求出。

单调递增栈可以一次确定右边界。扫描到 i 时，只要 nums[i] 不大于栈顶元素，就弹出下标 j：

i 是 j 右侧第一个不大于它的位置；

弹栈后的新栈顶是 j 左侧第一个严格小于它的位置；

因而 j 能扩展的最大区间是 (left, i)，区间和为 prefix[i] - prefix[left + 1]。

弹出相等元素相当于把相等最小值的完整区间交给靠右者计算，既不会漏掉最优区间，也避免边界归属含糊。扫描末尾再放一个虚拟的 0，把栈中剩余元素统一结算。

解题步骤

构造前缀和：prefix[i + 1] 表示前 i + 1 个数之和。

维护元素值严格递增的下标栈。

扫描 i = 0...n；当 i = n 时把当前值视为 0，作为结算哨兵。

当栈顶值不小于当前值时弹出 j，由新栈顶得到左边界，计算 nums[j] 对应的最大区间得分。

非哨兵位置入栈，最终返回所有贡献的最大值。

以 [1, 2, 3, 2] 为例，最后一个 2 到来时会依次结算 3 和前一个 2；末尾哨兵再结算后一个 2，其最大区间是 [2, 3, 2]，得分为 $2 × 7 = 14$。

代码实现

import java.util.ArrayDeque;
import java.util.Deque;

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)$。前缀和与单调栈各占线性空间。

关键点总结

将「枚举区间」改成「枚举哪个元素贡献最小值」，候选数从平方级降到线性级。

正数条件保证固定最小值后，扩张区间一定不会降低区间和；若允许负数，这个结论失效。

弹栈时右边界已经确定，弹栈后的栈顶恰好给出左边界，这是单调栈贡献法的核心。

前缀和及乘积必须使用 64 位整数；若题目要求取模，只能在求出真实最大值后取模，不能在比较前取模。

面试时要讲清相等元素的边界归属，而不是只背 >= 这个弹栈条件。

易错点总结

左右都找严格更小元素，却未规定相等值归属：重复元素会让边界判断不一致。

数组末尾不清栈：右侧没有更小元素的下标永远不会被计算。

把区间和写成 prefix[i] - prefix[left]：左边界是不可取位置，正确偏移是 left + 1。

用 32 位整数存前缀和或乘积：大数据会溢出。

忽略元素全为正的条件：有负数时，最大可扩展区间未必有最大区间和。

相似题目

题目	难度	考察点
84. 柱状图中最大的矩形	困难	同一母题的原型，权重从区间和退化为区间长度
85. 最大矩形	困难	把二维矩阵按行压成高度数组，再逐行套用柱状图解法
739. 每日温度	中等	单调栈最裸的形态，只求右侧最近更大元素的距离
907. 子数组的最小值之和	中等	同样枚举最小值，但要计数所有区间，重复元素的边界必须不对称
1504. 统计全 1 子矩形	中等	逐行维护连续 1 的高度，用单调栈累加以每列结尾的矩形数
LCR 039. 柱状图中最大的矩形	困难	可用来对照哨兵写法与循环内清算残余栈两种收尾方式
LCR 040. 最大矩形	困难	输入是字符矩阵，需先做前处理再复用高度数组套路