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;
};

參考資料