LeetCode 628. 三个数的最大乘积

Categories:

题目描述
思路分析
1. 解法一：一次遍历记录最大最小值（推荐）
相似题目

题目描述

✅ 628. 三个数的最大乘积

思路分析

解法一：一次遍历记录最大最小值（推荐）

核心思路：

最大乘积只可能来自两种情况：

最大的三个数相乘。

最小的两个数（可能为负）与最大数相乘。

一次遍历维护 max1 >= max2 >= max3 与 min1 <= min2。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(1)。

// 一次遍历维护最大最小值
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 x : nums) {
            if (x > max1) {
                max3 = max2;
                max2 = max1;
                max1 = x;
            } else if (x > max2) {
                max3 = max2;
                max2 = x;
            } else if (x > max3) {
                max3 = x;
            }

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

        return Math.max(max1 * max2 * max3, max1 * min1 * min2);
    }
}

// 一次遍历维护最大最小值
func maximumProduct(nums []int) int {
	max1, max2, max3 := -1<<31, -1<<31, -1<<31
	min1, min2 := 1<<31-1, 1<<31-1

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

		if x < min1 {
			min2 = min1
			min1 = x
		} else if x < min2 {
			min2 = x
		}
	}

	prod1 := max1 * max2 * max3
	prod2 := max1 * min1 * min2
	if prod2 > prod1 {
		return prod2
	}
	return prod1
}

相似题目

题目	难度	考察点
414. 第三大的数	简单	一次遍历
215. 数组中的第 K 个最大元素	中等	选择
238. 除自身以外数组的乘积	中等	前缀积
268. 丢失的数字	简单	数学
347. 前 K 个高频元素	中等	堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/77203467