628 三个数的最大乘积

本文最后更新于：2021年1月20日 上午

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

示例 1:

1
2
输入: [1,2,3]
输出: 6

示例 2:

1
2
输入: [1,2,3,4]
输出: 24

注意:

  1. 给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
  2. 输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。

Solution

先对数组进行排序，排序后的最大值由数组后三位相乘产生或者由前两位和最后一位相乘产生。

  • 当都为正数/负数，最大值由最后三位相乘产生。
  • 当有正有负时，最大值由最后三位或者前两位和最后一个正数相乘。
1
2
3
4
5
6
# @lc code=start
class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        return max(nums[-1]*nums[-2]*nums[-3], nums[0]*nums[1]*nums[-1])
# @lc code=end

@wo-xiang-zhao-gong-zuo——排序和非排序题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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)

cpp

1
2
3
4
5
6
7
8
9
10
// @lc code=start
class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        return max(nums[n-1]*nums[n-2]*nums[n-3], nums[0]*nums[1]*nums[n-1]);
    }
};
// @lc code=end
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！