【leetcode】 628. Maximum Product of Three Numbers

发表于 | 分类于 | 浏览 次
字数统计: 331 | 阅读时长 ≈ 2

题目

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example1:

Input: [1,2,3]
Output: 6

Example1:

Input: [1,2,3,4]
Output: 24

Note:
The length of the given array will be in range [3,$10^4$] 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.

分析

如果数组里面没有负整数，那最大的乘积就是三个最大的数字乘积，题目说明数组中的数字范围是[-1000, 1000]，所以会有两种情况：

  1. 两个最小的负数一个最大的正数
  2. 三个最大的正数相乘

所以只需要定义5个变量用来存储两个最小的和三个最大的数字，遍历一遍数组获取5个变量的值，然后返回两种情况中值较大的那种。

代码

int maximumProduct(vector<int>& nums) {
    //声明变量用来存储两个最小的数字和三个最大的数字
    int min1 = 1001, min2 = 1001, max1 = -1001, max2 = -1001, max3 = -1001;
    for (int i = 0; i < nums.size(); i++) {
        //遇到比min1还小的
        if (nums[i] < min1) {
            min2 = min1;
            min1 = nums[i];
        }
        else if (nums[i] < min2) {
            min2 = nums[i];
        }
        if (nums[i] > max1) {
            max3 = max2;
            max2 = max1;
            max1 = nums[i];
        }
        else if (nums[i] > max2) {
            max3 = max2;
            max2 = nums[i];
        }
        else if (nums[i] > max3) {
            max3 = nums[i];
        }
    }
    int x = min1*min2*max1;
    int y = max1*max2*max3;
    if (x > y)
        return x;
    else
        return y;
}

结果