628.三个数的最大乘积

• 628.三个数的最大乘积

• 题目：

  从数组nums中找出乘积最大的三个数；

  nums[i]∈[ -1000, 1000 ]，nums.size() ∈ [ 3, 10000 ]；

  乘积不会溢出；

• 思路：

  最大的情况一定是 最大的三个数 或 最小的两个数*最大的那个数；

  那就需要找出这两种情况

1.排序

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

2.不用排序，直接遍历一次，把所需的那几个数记录下来并不断更新；

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int min1 = INT32_MAX, min2 = INT32_MAX; //最小,次小
        int n1 = INT32_MIN, n2 = INT32_MIN, n3 = INT32_MIN; //最大,次大,次次大        
        for (auto x : nums) {
        	//更新最小，次小
            if (x < min1) {
                min2 = min1;
                min1 = x;
            }
            else if (x < min2) min2 = x;
			//更新最大
            if (x > n1) {
                n3 = n2;
                n2 = n1;
                n1 = x;
            }
            else if (x > n2) {
                n3 = n2;
                n2 = x;
            }
            else if (x > n3) {
                n3= x;
            }
        }
        return max(n1 * n2 * n3, min1 * min2 * n1);
    }
};