Easy

题目描述

给你一个整数数组 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

解题思路

解题思路

这道题要求找出数组中三个数的最大乘积。关键在于分析什么情况下能得到最大乘积。

核心观察： 要使三个数的乘积最大，只有两种可能的组合：

  1. 三个最大的正数：如果数组中有足够的正数
  2. 两个最小的负数 × 一个最大的正数：负负得正，可能比三个正数的乘积更大

解法一：排序法（推荐） 将数组排序后，最大乘积只可能出现在：

  • nums[n-1] × nums[n-2] × nums[n-3]（三个最大数）
  • nums[0] × nums[1] × nums[n-1]（两个最小数和一个最大数）

解法二：一次遍历法 不需要完整排序，只需要找到最大的三个数和最小的两个数即可。这种方法时间复杂度更优。

两种方法都能解决问题，但一次遍历法在大数据量时更高效。

代码实现

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        return max(nums[0] * nums[1] * nums[n-1], 
                   nums[n-1] * nums[n-2] * nums[n-3]);
    }
};

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        return max(nums[0] * nums[1] * nums[n-1],
                   nums[n-1] * nums[n-2] * nums[n-3])

public class Solution {
    public int MaximumProduct(int[] nums) {
        Array.Sort(nums);
        int n = nums.Length;
        return Math.Max(nums[0] * nums[1] * nums[n-1],
                        nums[n-1] * nums[n-2] * nums[n-3]);
    }
}

var maximumProduct = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    return Math.max(nums[0] * nums[1] * nums[n-1],
                    nums[n-1] * nums[n-2] * nums[n-3]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
排序法O(n log n)O(1)
一次遍历法O(n)O(1)

注：代码中给出的是排序法，因为代码更简洁易懂。如果追求最优时间复杂度，可以使用一次遍历找出最大三个数和最小两个数的方法。

相关题目