LeetCode 628. 三个数的最大乘积

2026-08-31 HGNULB 约 5 分钟

文章信息 14 个分类 3 个标签

分类

LeetCode CodeTop 简单未解决 10-20 字节跳动微软美团阿里巴巴腾讯猿辅导百度拼多多虾皮

题目描述

✅ 628. 三个数的最大乘积

题意分析

给一个长度至少为 3 的整数数组，从中任选三个不同位置的元素，返回它们乘积的最大值。

最关键的约束是元素可以为负（题目给的范围是 -1000 到 1000），这一点直接决定了答案的形态。如果数组全是非负数，最大乘积当然来自最大的三个数；但只要存在负数，「两个最小的负数乘以最大的正数」就可能反超——负负得正，两个绝对值很大的负数相乘会变成一个很大的正数。例如 [-100, -98, 1, 2, 3]，最大的三个数给出 1 * 2 * 3 = 6，而 (-100) * (-98) * 3 = 29400 才是答案。

另外两个信号：数组长度可以到 $10^4$，所以三重枚举的量级不可接受；元素绝对值不超过 1000，三个数乘积最大约 $10^9$，稳稳落在 int 范围内，不需要升到 long。

边界包括：长度恰好为 3（只有一种选法，答案就是它们的乘积）、全部为负数、数组里含 0、大量重复值。

解法：维护三个最大值和两个最小值

核心思路

将数组升序记为 $a_0 \le a_1 \le \cdots \le a_{n-1}$，最大乘积只可能来自两个候选：

最大的三个数：$a_{n-1}a_{n-2}a_{n-3}$；

最大的数与最小的两个数：$a_{n-1}a_0a_1$。

证明按符号分类即可。正乘积要么由三个正数产生，此时应取最大的三个数；要么由一个正数和两个负数产生，此时正数越大越好，两个负数越小、绝对值越大，负负相乘越大。若无法得到正乘积，全负数组的最优选择是最接近 0 的三个数，也包含在第一个候选中；0 的情况同样会被两者覆盖。

因此无需排序，只需一次扫描维护三个最大值 max1 >= max2 >= max3 和两个最小值 min1 <= min2。扫描结束后比较上述两个候选即可。

解题步骤

将三个最大值初始化为整数最小值，两个最小值初始化为整数最大值。

扫描每个 num，按从大到小的顺序更新三个最大值；插入新值时，原有名次依次后移。

同一轮独立更新两个最小值，不能与最大值更新写成互斥分支。

计算 max1 * max2 * max3 与 max1 * min1 * min2，返回较大者。

例如 [-4, -3, -2, 1, 60] 扫描后，三个最大值是 60、1、-2，两个最小值是 -4、-3。两个候选分别为 -120 和 720，答案是 720。

代码实现

class Solution {
    public int maximumProduct(int[] nums) {
        int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        int max3 = Integer.MIN_VALUE;
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;

        for (int num : nums) {
            if (num >= max1) {
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (num >= max2) {
                max3 = max2;
                max2 = num;
            } else if (num > max3) {
                max3 = num;
            }

            if (num <= min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        }

        int threeLargest = max1 * max2 * max3;
        int twoSmallest = max1 * min1 * min2;
        return Math.max(threeLargest, twoSmallest);
    }
}

func maximumProduct(nums []int) int {
    maxInt := int(^uint(0) >> 1)
    minInt := -maxInt - 1
    max1, max2, max3 := minInt, minInt, minInt
    min1, min2 := maxInt, maxInt

    for _, num := range nums {
        if num >= max1 {
            max3, max2, max1 = max2, max1, num
        } else if num >= max2 {
            max3, max2 = max2, num
        } else if num > max3 {
            max3 = num
        }

        if num <= min1 {
            min2, min1 = min1, num
        } else if num < min2 {
            min2 = num
        }
    }

    threeLargest := max1 * max2 * max3
    twoSmallest := max1 * min1 * min2
    if threeLargest > twoSmallest {
        return threeLargest
    }
    return twoSmallest
}

复杂度分析

时间复杂度：$O(n)$。数组只扫描一次，每个元素执行常数次比较和赋值。

空间复杂度：$O(1)$。只维护五个极值和两个候选乘积。

关键点总结

负数使答案多出“两个最小值乘最大值”这一候选，不能只取最大的三个数。

两个候选的完备性来自乘积符号分类，而不是经验枚举。

更新极值时必须整体后移，确保每个数组位置只占一个名次，同时正确保留重复值。

题目数值范围保证三个数的乘积落在 32 位整数内；若范围扩大，Java 应先转为 long 再相乘。

易错点总结

只计算最大的三个数：[-100, -98, 1, 2, 3] 会错过 (-100) * (-98) * 3。

看到负数就固定选择两负一正：全负数组 [-5, -4, -3, -2] 的答案应是 (-4) * (-3) * (-2)。

更新最大值时不把旧值后移，会丢失第二、第三大值。

最大值与最小值更新写成同一条 if / else if 链，可能导致某个元素只参与其中一组更新。

忽略数值范围直接使用较窄类型；题目范围内 int 安全，通用实现应先检查乘积是否可能溢出。

相似题目

题目	难度	考察点
1464. 数组中两元素的最大乘积	简单	双极值维护
215. 数组中的第K个最大元素	中等	快速选择
152. 乘积最大子数组	中等	正负极值同步 DP
238. 除了自身以外数组的乘积	中等	前后缀积