原文链接: https://leetcode-cn.com/problems/maximum-product-of-three-numbers

英文原文

Given an integer array nums, find three numbers whose product is maximum and return the maximum product.

 

Example 1:

Input: nums = [1,2,3]
Output: 6

Example 2:

Input: nums = [1,2,3,4]
Output: 24

Example 3:

Input: nums = [-1,-2,-3]
Output: -6

 

Constraints:

• 3 <= nums.length <= 104
• -1000 <= nums[i] <= 1000

中文题目

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

 

示例 1：

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

示例 2：

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

示例 3：

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

 

提示：

• 3 <= nums.length <= 104
• -1000 <= nums[i] <= 1000

通过代码

高赞题解

解题思路

排序法：数组可以分为三种情况，第一是都为正数，第二是都为负数，第三是有正有负（分为（1）只有一个负数（2）有两个及以上的负数）
都为正数：乘积最大值为排序数组最后三个数相乘
都为负数：乘积最大值为排序数组最后三个数相乘
有正有负：（1）乘积最大值为排序数组最后三个数相乘
（2）乘积最大值为排序数组前两个负数与数组最后一个正数相乘
整理一下上面的四种情况：可以归纳成取max（排序数组最后三个数相乘，排序数组前两个负数与数组最后一个正数相乘）
不排序方法：通过上面对排序法的分析，我们可以看出，实际上我们只要找到数组的第一大的值，第二大的值，第三大的值，第一小的值和第 二小的值即可。所以我们只需要遍历一边数组，即可找到这些值（具体实现看代码注释）！

代码

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        """排序方法，时间复杂度O(nlog(n))"""
        # nums.sort()
        # return max(nums[-1] * nums[-2] * nums[-3], nums[-1] * nums[0] * nums[1])

        """遍历一遍数组，不使用排序，时间复杂度O(n)"""
        max1 = -float('inf')       # 第一大的值
        max2 = -float('inf')       # 第二大的值
        max3 = -float('inf')       # 第三大的值
        min1 = float('inf')        # 第一小的值
        min2 = float('inf')        # 第二小的值

        for num in nums:
            if num > max1:         # 啥？你比第一大的值还大？？那好吧，你去做老大
                max3 = max2        # 原老二委屈一下你，去做老三吧，难受...
                max2 = max1        # 原老大委屈一下你，去做老二吧，很难受...
                max1 = num         # 大哥快请上座！！！
            elif num > max2:       # 嗯？你比第二大的值大啊？？那行吧，老二给你做，别碰老大啊，他脾气不好...
                max3 = max2        # 原老二委屈一下你，去做老三吧，难受...
                max2 = num         # 二哥请上座！！
            elif num > max3:       # 别舞舞喳喳的，不就比第三大的值大么？？去去去，那个位置给你了...
                max3 = num         # 三哥上座！
            
            if num < min1:         # 啊？你比第一小的值还小，哈哈哈，笑死我了，来来来，快去！
                min2 = min1        # 原第一小，恭喜你，终于找到比你小的了，你现在是第二小！
                min1 = num         # 老实呆着，你现在是最小的了！！！
            elif num < min2:       # 哦？你比第二小的值小？比最小的还大，嗯..那你去做第二小
                min2 = num         # 来吧，你现在是第二小，原第二小解脱了！
            
        return max(max1 * max2 * max3, max1 * min1 * min2)

统计信息

通过次数	提交次数	AC比率
83205	158724	52.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
乘积最大子数组	中等