当前位置：首页 > news >正文

LeetCode题练习与总结：三个数的最大乘积--628

news 2025/7/3 16:23:35

一、题目描述

给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1：

输入：nums = [1,2,3]
输出：6

示例 2：

输入：nums = [1,2,3,4]
输出：24

示例 3：

输入：nums = [-1,-2,-3]
输出：-6

提示：

3 <= nums.length <= 10^4
-1000 <= nums[i] <= 1000

二、解题思路

对数组进行排序。
考虑到负数乘以负数会得到正数，所以最大的乘积可能由两种情况产生：
- 最大的三个正数相乘。
- 最小的两个负数（它们相乘得到正数）和最大的正数相乘。
比较这两种情况得到的乘积，取较大的一个作为结果。

三、具体代码

import java.util.Arrays;class Solution {public int maximumProduct(int[] nums) {// 对数组进行排序Arrays.sort(nums);// 数组长度int n = nums.length;// 最大的三个数相乘int product1 = nums[n - 1] * nums[n - 2] * nums[n - 3];// 最小的两个数（可能为负数）和最大的数相乘int product2 = nums[0] * nums[1] * nums[n - 1];// 返回两种情况中较大的乘积return Math.max(product1, product2);}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

排序操作：Arrays.sort(nums) 是一个通用的排序算法，通常基于快速排序或归并排序实现，其平均时间复杂度为 O(n log n)，其中 n 是数组 nums 的长度。
计算乘积：在排序后，计算两个乘积 product1 和 product2 的时间复杂度是 O(1)，因为这些操作都是常数时间的操作。

因此，整个函数的时间复杂度主要取决于排序操作，为 O(n log n)。

2. 空间复杂度

排序操作：Arrays.sort(nums) 在最坏情况下可能需要 O(log n) 的空间复杂度，这是由于递归调用栈的深度。不过，对于大多数实现，这个空间复杂度可以认为是 O(1)，因为它们使用了原地排序算法。
临时变量：除了输入数组 nums 以外，我们使用了常数个额外空间（n, product1, product2），因此这部分的空间复杂度是 O(1)。

综合上述分析，整个函数的空间复杂度是 O(1)，即常数空间复杂度。

五、总结知识点

类定义：
- class 关键字用于定义一个类。
- Solution 是类的名称。
方法定义：
- public 关键字指定方法的访问修饰符，表示该方法可以被任何其他类访问。
- int 表示方法返回值的类型。
- maximumProduct 是方法的名称。
- int[] nums 是方法的参数，表示一个整型数组。
数组排序：
- Arrays.sort(nums) 是一个静态方法调用，用于对数组 nums 进行排序。
数组操作：
- nums.length 用于获取数组的长度。
- nums[n - 1]、nums[n - 2]、nums[n - 3] 等用于访问数组中的元素。
基本数据类型和算术运算：
- int 是 Java 中的基本数据类型，用于表示整数。
- * 是乘法运算符，用于计算两个整数的乘积。
条件判断和返回值：
- Math.max(product1, product2) 是一个静态方法调用，用于计算两个整数中的最大值。
- return 语句用于从方法中返回一个值。