LeetCode 628. 三个数的最大乘积

约 5 分钟
文章信息 14 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 腾讯 字节 阿里 微软 美团 拼多多 百度 虾皮 猿辅导
标签
数组 数学 排序

题目描述

✅ 628. 三个数的最大乘积

image-20260928215849175

题意分析

从数组的不同位置选出三个元素，使乘积最大，不要求它们连续。相同数值可以重复选择，但必须来自不同位置。题面保证至少有三个元素，且每个元素都在 $[-1000,1000]$ 内。

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

核心思路

[!blue]

如果最大乘积为正，它只可能来自三个正数或两负一正。三个正数应取最大的三个；两负一正则应取最小的两个负数，让它们的乘积尽量大，再乘最大的正数。因此只需比较 max1 * max2 * max3 和 max1 * min1 * min2。

这两个候选也覆盖非正答案：全负时，最大的三个数绝对值最小，乘积最接近零；不能得到正乘积但存在零时，候选中包含零乘积。正负混合、没有零却只能得到负乘积的情况，只可能是两个正数和一个负数，此时两个候选就是唯一的三元组。

无需真的排序，只在扫描中维护 max1 >= max2 >= max3 和 min1 <= min2。它们分别是已扫描元素的前三大和前两小，重复值按出现次数占位。新值进入某个名次时，先向后移动被挤下的旧值；最大值组和最小值组独立更新，才能同时保持两组状态。

解题步骤

  1. 将三个最大值初始化为整数最小值，两个最小值初始化为整数最大值。
  2. 扫描每个 num，按从大到小的顺序更新三个最大值；插入新值时，原有名次依次后移。
  3. 同一轮独立更新两个最小值，不能与最大值更新写成互斥分支。
  4. 计算 max1 * max2 * max3 与 max1 * min1 * min2，返回较大者。

代码实现

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)$。只维护五个极值和两个候选乘积。

关键点总结

[!green]

  • 负数使答案多出“两个最小值乘最大值”这一候选，不能只取最大的三个数。
  • 两个候选的完备性来自乘积符号分类，而不是经验枚举。
  • 更新极值时必须整体后移，确保每个数组位置只占一个名次，同时正确保留重复值。
  • 题面中元素绝对值不超过 1000，三个数的乘积绝对值不超过 $10^9$，现有 32 位整数计算足够。

易错点总结

[!yellow]

  • 只计算最大的三个数，会错过两个绝对值很大的负数带来的正乘积。
  • 看到负数就固定选择两个最小值：全负时应让乘积尽量接近零，答案来自最大的三个数。
  • 更新最大值时不把旧值后移，会丢失第二、第三大值。
  • 最大值与最小值更新写成同一条 if / else if 链，可能导致某个元素只参与其中一组更新。
  • 相同数值来自不同位置时仍应占据不同名次，不能把极值去重。

相似题目

题目 难度 关联与区别
414. 第三大的数 简单 最大的三个数是候选之一，但本题还必须保留最小的两个负数，因为负负相乘可能更大。
152. 乘积最大子数组 中等 同样因负号需要同时考虑最大与最小值，本题任选三项，原题要求连续子数组。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/77203467
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！