628. Maximum Product of Three Numbers

Leetcode 问题: 628. Maximum Product of Three Numbers
Categories:
Tags:

题目

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

传入一个正负整数阵列 nums，找到三个数字的乘积和是最大的

数字可能为正也可能为负，所以要考虑负数状况

Example

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

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

Input: nums = [-1,-2,-3]
Output: -6

演算法 1: 阵列排序取前后乘积最大

1. 数字阵列由大到小排序

将数字排序后，就可以从知道乘积最大的数字在哪裡，可以直接运算

2. 取得前后数字乘积最大的数字

前面最大的数字乘积：数字最大的 3 个数相乘

后面最大的乘积：最大的数字，与最后面的 2 个数字相乘

因为会有负数的状况，所以如果有 2 个很大的负数，相乘后的数字也是会比较大，所以要拿出来比较

然后 前面最大的数字乘积 与 后面最大的乘积 取最大即可

演算法 1: 答案

JavaScript

function maximumProduct(numsList) {
    // 由大到小排序
    numsList.sort(function (a, b) {
        return b - a;
    });
    // 前面最大的数字乘积
    var prefixMaxProductNumber = numsList[0] * numsList[1] * numsList[2];
    // 后面最大的乘机（拿取两个可能的负数）
    var postfixMaxProductNumber = numsList[0] * numsList[numsList.length - 1] * numsList[numsList.length - 2];
    // 「前面最大数字乘积」与「后面最大数字乘积」取最大
    var maxProductNumber = Math.max(prefixMaxProductNumber, postfixMaxProductNumber);
    return maxProductNumber;
}

TypeScript

function maximumProduct(numsList: number[]): number {
    // 由大到小排序
    numsList.sort(function(a, b) {
        return b - a;
    });

    // 前面最大的数字乘积
    let prefixMaxProductNumber = numsList[0] * numsList[1] * numsList[2];
    // 后面最大的乘机（拿取两个可能的负数）
    let postfixMaxProductNumber = numsList[0] * numsList[numsList.length - 1] * numsList[numsList.length - 2];

    // 「前面最大数字乘积」与「后面最大数字乘积」取最大
    let maxProductNumber = Math.max(prefixMaxProductNumber, postfixMaxProductNumber);

    return maxProductNumber;
};

演算法 2: 直接判断数字大小，取前三大，及前二小数字

判断数字大小取前三大，及前二小数字

单纯使用 if 判断数字大小，将前三大，及前二小数字都抓出来

2. 取得前后数字乘积最大的数字

前面最大的数字乘积：数字最大的 3 个数相乘

后面最大的乘积：最大的数字，与最后面的 2 个数字相乘

因为会有负数的状况，所以如果有 2 个很大的负数，相乘后的数字也是会比较大，所以要拿出来比较

然后 前面最大的数字乘积 与 后面最大的乘积 取最大即可

演算法 2: 答案

JavaScript

function maximumProduct(numsList) {
    var maxNumber1 = -Infinity;
    var maxNumber2 = -Infinity;
    var maxNumber3 = -Infinity;
    var minNumber1 = Infinity;
    var minNumber2 = Infinity;
    for (var i = 0; i < numsList.length; i++) {
        // 目前数字
        var currentNumber = numsList[i];
        if (currentNumber > maxNumber1) {
            maxNumber3 = maxNumber2;
            maxNumber2 = maxNumber1;
            maxNumber1 = currentNumber;
        }
        else if (currentNumber > maxNumber2) {
            maxNumber3 = maxNumber2;
            maxNumber2 = currentNumber;
        }
        else if (currentNumber > maxNumber3) {
            maxNumber3 = currentNumber;
        }
        if (currentNumber < minNumber1) {
            minNumber2 = minNumber1;
            minNumber1 = currentNumber;
        }
        else if (currentNumber < minNumber2) {
            minNumber2 = currentNumber;
        }
    }
    // 前面最大的数字乘积
    var prefixMaxProductNumber = maxNumber1 * maxNumber2 * maxNumber3;
    // 后面最大的乘积（拿取两个可能的负数）
    var postfixMaxProductNumber = maxNumber1 * minNumber1 * minNumber2;
    // 「前面最大数字乘积」与「后面最大数字乘积」取最大
    var maxProductNumber = Math.max(prefixMaxProductNumber, postfixMaxProductNumber);
    return maxProductNumber;
}

TypeScript

function maximumProduct(numsList: number[]): number {
    let maxNumber1: number = -Infinity;
    let maxNumber2: number = -Infinity;
    let maxNumber3: number = -Infinity;
    let minNumber1: number = Infinity;
    let minNumber2: number = Infinity;

    for (let i = 0; i < numsList.length; i++) {
        // 目前数字
        let currentNumber = numsList[i];
        if (currentNumber > maxNumber1) {
            maxNumber3 = maxNumber2;
            maxNumber2 = maxNumber1;
            maxNumber1 = currentNumber;
        } else if (currentNumber > maxNumber2) {
            maxNumber3 = maxNumber2;
            maxNumber2 = currentNumber;
        } else if (currentNumber > maxNumber3) {
            maxNumber3 = currentNumber
        }

        if (currentNumber < minNumber1) {
            minNumber2 = minNumber1;
            minNumber1 = currentNumber;
        } else if (currentNumber < minNumber2) {
            minNumber2 = currentNumber
        }
    }

    // 前面最大的数字乘积
    let prefixMaxProductNumber = maxNumber1 * maxNumber2 * maxNumber3
    // 后面最大的乘积（拿取两个可能的负数）
    let postfixMaxProductNumber = maxNumber1 * minNumber1 * minNumber2;

    // 「前面最大数字乘积」与「后面最大数字乘积」取最大
    let maxProductNumber = Math.max(prefixMaxProductNumber, postfixMaxProductNumber);

    return maxProductNumber;
};

参考资料