leetcode: 628. Maximum Product of Three Numbers

淩亂°似流年 2022-06-13 11:12 192阅读 0赞

# 1.题目 #

Given an integer array, find three numbers whose product is maximum and output the maximum product.  
一个数组，长度\[3,104\]，找出其中三个元素使得它们的乘积最大。返回乘积最大值。  
Example 1:  
Input: \[1,2,3\]  
Output: 6

Example 2:  
Input: \[1,2,3,4\]  
Output: 24  
注意：乘积的范围不会超过INT32  
Note:  
The length of the given array will be in range \[3,104\] and all elements are in the range \[-1000, 1000\].  
Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.

# 2.分析 #

乘积最大值大致分两种情况：  
a. 数组中最大的三个正数  
b.数组中最小的两个负数和最大的正数

所以目标是找出数组的前三大的数和前2最小的数。然后比较乘积大小。

# 3.代码 #

可以一次遍历通过比较得到最大最小值

class Solution {
    public:
        int maximumProduct(vector<int>& nums) {
            int max_1 = INT_MIN;
            int max_2 = INT_MIN;
            int max_3 = INT_MIN;
            int min_1 = INT_MAX;
            int min_2 = INT_MAX;
            for (auto n : nums) {
                if (n > max_1) {
                    max_3 = max_2;
                    max_2 = max_1;
                    max_1 = n;
                }
                else if (n > max_2) {
                    max_3 = max_2;
                    max_2 = n;
                }
                else if (n > max_3)
                    max_3 = n;
                if (n < min_1)
                {
                    min_2 = min_1;
                    min_1 = n;
                }
                else if (n < min_2)
                    min_2 = n;
            }
            return max(max_1*max_2*max_3, max_1*min_1*min_2);
        }
    };

或者直接排序，O(nlogn)

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