【LeetCode】628.三个数的最大乘积

• 题目描述

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

• 思路

可能组成最大乘积的三个数有两种可能。可能一：最大的三个正数的乘积；可能二：最大的正数与最小的两个负数的乘积。因此遍历数组，找出这5个数，比较可能的两个结果，较大的那个就是我们要返回的。

在单次扫描中，找出最大的三个数：

如果新的数大于最大的数，那么将最大的数移动到次大的位置，将次大的数移动到第三大的位置，并将新数插入到最大位置处。

如果性的数小于最大的数，但大于次大的数，则依次将次大的数移到第三大的位置，并将新数插入次大的位置；以此类推。

• C++实现

    int maximumProduct(vector<int>& nums){
        int size = nums.size();
        int firstMin = INT_MAX, secondMin = INT_MAX;
        int firstMax = INT_MIN, secondMax = INT_MIN, thirdMax = INT_MIN;
        for(auto num:nums){
            // 更新最大值
            if(num>=firstMax){
                thirdMax = secondMax;
                secondMax = firstMax;
                firstMax = num;
            }else if(num>=secondMax){
                thirdMax = secondMax;
                secondMax = num;
            }else if(num>thirdMax){
                thirdMax = num;
            }
            
            // 更新最小值
            if(num<=firstMin){
                secondMin = firstMin;
                firstMin = num;
            }else if(num<secondMin){
                secondMin = num;
            }
        }
        return max(firstMax*secondMax*thirdMax,firstMin*secondMin*firstMax);
    }