leecode 628. 三個數的最大乘積

題目描述

給你一個整型數組 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

連結：https://leetcode-cn.com/problems/maximum-product-of-three-numbers

要求時間複雜度為O(n)，空間複雜度為O(1)

隻需要找到最大的三個數字，對于序列中隻有正數而言的序列，就需要找序列中絕對值最大的數，對于序列中含有負數的序列，就需要找兩個最小的負數以及一個最大的正數，總結下來就是找最大的三個數以及最小的兩個數，此時用到的空間為常數，是以為O(1),時間複雜度為O(n)，因為需要循環周遊一遍整個數組。初始化時，max1，max2,max3初始化為INT_MIN，min1，min2初始化為INT_MAX。這些數字尋找的過程是對于最小的數而言，想用該數字與最小的數字比，如果最小的數字小于目前min1，那麼需要更新min1和min2；對于尋找最大的數字而言，就要用該數字與max1先作比較，如果該數字比max1大的話，就需要更新max1。最後取兩個最小數字與最大數字的乘積以及三個最大數字乘積這兩個數值的最大值。

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int max1=INT_MIN,max2=INT_MIN,max3=INT_MIN;
        int min1=INT_MAX,min2=INT_MAX;
        for(auto x:nums)
        {
            if(x < min1)
            {
                min2 = min1;
                min1 = x;
            }
            else if(x < min2)
            {
                min2 = x;
            }

            if(x > max1)
            {
                max3 = max2;
                max2 = max1;
                max1 = x;
            }
            else if( x > max2)
            {
                max3 = max2;
                max2 = x;
            }
            else if(x > max3)
            {
                max3 = x;

            }
        }
        return max(min1*min2*max1 , max1*max2*max3);
    }
};

           

如果沒有時間複雜度的限制，那麼正常的做法是sort，排序之後直接找三個最大正數的乘積，以及兩個最小負數與最大正數的乘積，取二者之間的最大值即可。

牛客網上的樣例沒有限制數組中數字的取值範圍，需要在結果輸出時做資料類型的轉化，将int轉化為 long long。