LeetCode - 3 つの数値の最大積

問題文

整数配列 nums を指定して、積が最大になる 3 つの数値を見つけ、最大の積を返します.

問題の説明: https://leetcode.com/problems/maximum-product-of-three-numbers

例 1:

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

例 2:

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

例 3:

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

制約:

- 3 <= nums.length <= 10^4
- -1000 <= nums[i] <= 1000

説明

この問題を解決する方法は複数あります.最悪のケースから最良のケースまで、すべてのソリューションを調べてみましょう.

ブルート フォース: 3 つのネストされたループ

簡単な解決策は、3 つのネストされたループを使用して、配列のすべてのトリプレットをチェックすることです.

このアプローチの C++ スニペットは次のようになります.

for (int i = 0; i < n - 2; i++)
    for (int j = i + 1; j < n - 1; j++)
        for (int k = j + 1; k < n; k++)
            max_product = max(max_product, arr[i] * arr[j] * arr[k]);

上記のように、時間の複雑さは O(N^3) であり、空間の複雑さは O(1) です.

追加スペースの使用

追加のスペースを使用して、時間の複雑さを O(N) に減らすことができます.

入力配列と同じサイズの 4 つの配列 leftMax[]、rightMax[]、leftMin[]、rightMin[] を作成します.

上記の 4 つの配列を次のように入力します.

leftMax[i] には、arr[i] を除く arr[i] の左側の最大要素が含まれます.インデックス 0 の場合、左には -1 が含まれます.

leftMin[i] には、arr[i] を除く arr[i] の左側の最小要素が含まれます.インデックス 0 の場合、左には -1 が含まれます.

rightMax[i] には、arr[i] を除く arr[i] の右側の最大要素が含まれます.インデックス n - 1 の場合、right には -1 が含まれます.

rightMin[i] には、arr[i] を除く arr[i] の右側の最小要素が含まれます.インデックス n - 1 の場合、right には -1 が含まれます.

最初と最後のインデックスを除くすべての配列インデックス i について、arr[i]*x*y の最大値を計算します.ここで、x は leftMax[i] または leftMin[i]、y は rightMax[i] または rightMin[i] です.

ステップ 3 から最大値を返します.

このアプローチの C++ スニペットは次のようになります.

vector<int> leftMin(n, -1);
vector<int> rightMin(n, -1);
vector<int> leftMax(n, -1);
vector<int> rightMax(n, -1);

for (int i = 1; i < n; i++){
    leftMax[i] = max_sum;
    if (arr[i] > max_sum)
        max_sum = arr[i];

    leftMin[i] = min_sum;
    if (arr[i] < min_sum)
        min_sum = arr[i];
}

for (int j = n - 2; j >= 0; j--){
    rightMax[j] = max_sum;
    if (arr[j] > max_sum)
        max_sum = arr[j];

    rightMin[j] = min_sum;
    if (arr[j] < min_sum)
        min_sum = arr[j];
}

for (int i = 1; i < n - 1; i++){
    int max1 = max(arr[i] * leftMax[i] * rightMax[i], arr[i] * leftMin[i] * rightMin[i]);
    int max2 = max(arr[i] * leftMax[i] * rightMin[i], arr[i] * leftMin[i] * rightMax[i]);

    max_product = max(max_product, max(max1, max2));
}

このアプローチのスペースの複雑さは O(N) です.

ソートの使用

配列をソートすることでスペースの複雑さを軽減し、配列の最後の 3 つの要素の積と、最初の 2 つの要素と最後の要素の積との間の最大値を考慮することができます.

このアプローチの C++ スニペットは次のようになります.

sort(arr, arr + n);

return max(arr[0] * arr[1] * arr[n - 1], arr[n - 1] * arr[n - 2] * arr[n - 3]);

このアプローチの時間計算量は O(NlogN) で、空間計算量は O(N) です.

5 つの変数の使用

この問題は、5 つの変数を使用して解決できます. 3 つの変数が最大値を配列に格納します.残りの 2 つは、配列に存在する最小値を格納します.

アルゴリズムを確認しましょう:

- set max1, max2 and max3 to INT_MIN
  set min1, min2 to INT_MAX

- loop for i = 0; i < nums.size(); i++
  - if nums[i] < min1
    - set min2 = min1
    - set min1 = nums[i]
  - else if nums[i] < min2
    - set min2 = nums[i]

  - if nums[i] > max1
    - set max3 = max2
    - set max2 = max1
    - set max1 = nums[i]
  - else if nums[i] > max2
    - set max3 = max2
    - set max2 = nums[i]
  - else if nums[i] > max3
    - set max3 = nums[i]

- return max(min1 * min2 * max1, max1 * max2 * max3)

C++ ソリューション

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
        int min1 = INT_MAX, min2 = INT_MAX;

        for(int i = 0; i < nums.size(); i++){
            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];
            }
        }

        return max(min1*min2*max1, max1*max2*max3);
    }
};

Golang ソリューション

const MAXINT = math.MaxInt32
const MININT = math.MinInt32

func maximumProduct(nums []int) int {
    max1, max2, max3 := MININT, MININT, MININT
    min1, min2 := MAXINT, MAXINT

    for i := 0; i < len(nums); i++ {
        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]
        }
    }

    return int(math.Max(float64(min1 *min2 * max1), float64(max1 * max2 * max3)))
}

Javascript ソリューション

var maximumProduct = function(nums) {
    let min1 = Number.POSITIVE_INFINITY, min2 = Number.POSITIVE_INFINITY;
    let max1 = Number.NEGATIVE_INFINITY, max2 = Number.NEGATIVE_INFINITY, max3 = Number.NEGATIVE_INFINITY;

    for(let i = 0; i < nums.length; i++) {
        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];
        }
    }

    return Math.max(min1 * min2 * max1, max1 * max2 * max3 );
};

アルゴリズムをドライランして、ソリューションがどのように機能するかを見てみましょう.

Input: nums = [-6, 5, 1, 2, 3, -4, 9]

Step 1: int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
        int min1 = INT_MAX, min2 = INT_MAX;

Step 2: loop for int i = 0; i < nums.size()
        i < nums.size()
        0 < 7
        true

        if nums[i] < min1
           nums[0] < INT_MAX
           -6 < INT_MAX
           true

           - min2 = min1
                  = INT_MAX
           - min1 = nums[i]
                  = nums[0]
                  = -6

        if nums[i] > max1
           nums[0] > INT_MIN
           -6 > INT_MIN
           true

           - max3 = max2
                  = INT_MIN
           - max2 = max1
                  = INT_MIN
           - max1 = nums[i]
                  = nums[0]
                  = -6

        i++
        i = 1

Step 3: loop for int i = 0; i < nums.size()
        i < nums.size()
        1 < 7
        true

        if nums[i] < min1
           nums[1] < INT_MAX
           1 < -6
           false
        else if nums[i] < min2
           5 < INT_MAX
           true

           - min2 = nums[i]
                  = 5


        if nums[i] > max1
           nums[1] > -6
           5 > -6
           true

           - max3 = max2
                  = INT_MIN
           - max2 = max1
                  = -6
           - max1 = nums[i]
                  = nums[1]
                  = 5

        i++
        i = 2

Step 4: loop for int i = 0; i < nums.size()
        i < nums.size()
        2 < 7
        true

        if nums[i] < min1
           nums[2] < -6
           1 < -6
           false
        else if nums[i] < min2
           1 < 5
           true

           - min2 = nums[2]
                  = 1


        if nums[i] > max1
           nums[2] > 5
           1 > 5
           false

        else if nums[i] > max2
           nums[2] > -6
           1 > -6
           true

           - max3 = max2
                  = -6
           - max2 = nums[i]
                  = nums[2]
                  = 1

        i++
        i = 3

Step 5: loop for int i = 0; i < nums.size()
        i < nums.size()
        3 < 7
        true

        if nums[i] < min1
           nums[3] < -6
           2 < -6
           false
        else if nums[i] < min2
           2 < 1
           false

        if nums[i] > max1
           nums[3] > 5
           2 > 5
           false

        else if nums[i] > max2
           nums[3] > 1
           2 > 1
           true

           - max3 = max2
                  = 1
           - max2 = nums[i]
                  = nums[3]
                  = 2

        i++
        i = 4

Step 6: loop for int i = 0; i < nums.size()
        i < nums.size()
        4 < 7
        true

        if nums[i] < min1
           nums[4] < -6
           3 < -6
           false
        else if nums[i] < min2
           3 < 1
           false

        if nums[i] > max1
           nums[4] > 5
           3 > 5
           false

        else if nums[i] > max2
           nums[4] > 2
           3 > 2
           true

           - max3 = max2
                  = 2
           - max2 = nums[i]
                  = nums[4]
                  = 3

        i++
        i = 5

Step 7: loop for int i = 0; i < nums.size()
        i < nums.size()
        5 < 7
        true

        if nums[i] < min1
           nums[5] < -6
           -4 < -6
           false
        else if nums[i] < min2
           -4 < 1
           true

           - min2 = nums[i]
                  = -4

        if nums[i] > max1
           nums[5] > 5
           -4 > 5
           false

        else if nums[i] > max2
           nums[5] > 3
           -4 > 3
           false

        else if nums[i] > max3
           nums[5] > 2
           -4 > 2
           false

        i++
        i = 6

Step 8: loop for int i = 0; i < nums.size()
        i < nums.size()
        6 < 7
        true

        if nums[i] < min1
           nums[6] < -6
           9 < -6
           false
        else if nums[i] < min2
           9 < -4
           false

        if nums[i] > max1
           nums[6] > 5
           9 > 5
           true

           - max3 = max2
                  = 3
           - max2 = max1
                  = 5
           - max1 = nums[i]
                  = nums[6]
                = 9

        i++
        i = 7

Step 9: loop for int i = 0; i < nums.size()
        i < nums.size()
        7 < 7
        false

Step 10: return max(min1 * min2 * max1, max1 * max2 * max3)
                max(-6 * -4 * 9, 9 * 5 * 3)
                max(216, 135)
                = 216

So we return the answer as 216.