題目

標題和出處

標題：三個數的最大乘積

出處：628. 三個數的最大乘積

難度

3 級

題目描述

要求

給定一個整數數組 $\text{nums}$，在數組中找出三個數，使得這三個數的乘積最大，并返回最大乘積。

示例

示例 1：

輸入：$\text{nums?=?[1,2,3]}$
輸出：$\text{6}$

示例 2：

輸入：$\text{nums?=?[1,2,3,4]}$
輸出：$\text{24}$

示例 3：

輸入：$\text{nums?=?[-1,-2,-3]}$
輸出：$\text{-6}$

數據范圍

• $\text{3}\le \text{nums.length}\le {\text{10}}^{\text{4}}$
• $\text{-1000}\le \text{nums[i]}\le \text{1000}$

解法一

思路和算法

由于數組 $\text{nums}$ 中可能存在正數、零與負數，因此需要考慮當乘積最大時的三個數的所有可能情況。

• 如果數組中的所有元素都是非負數，則任意三個數的乘積都是非負數，數組中的最大三個數的乘積即為最大乘積。

• 如果數組中的所有元素都是負數，則任意三個數的乘積都是負數，為了使乘積最大應該使乘積的絕對值最小，數組中的最大三個數即為絕對值最小的三個數，乘積即為最大乘積。

• 如果數組中同時有非負數與負數，則根據負數的個數，有兩種可能的情況。

  • 如果數組中至少有兩個負數，則當乘積最大時，最大乘積一定是非負數。可能選三個最大的非負數，也可能選一個最大的非負數與兩個最小的負數（即兩個絕對值最大的負數）。

  • 如果數組中只有一個負數，則任意三個數中至少有兩個非負數，當乘積最大時，一定是選數組中的最大三個數。

根據上述分析可知，當乘積最大時，三個數的可能情況有兩種，一是選數組中最大的三個數，二是選數組中最大的一個數與最小的兩個數。對于這兩種情況分別計算乘積，返回最大乘積。

代碼

class Solution {public int maximumProduct(int[] nums) {Arrays.sort(nums);int length = nums.length;return Math.max(nums[length - 3] * nums[length - 2] * nums[length - 1], nums[0] * nums[1] * nums[length - 1]);}
}

復雜度分析

• 時間復雜度：$O(n\log n)$，其中 $n$ 是數組 $\text{nums}$ 的長度。排序需要 $O(n\log n)$ 的時間。

• 空間復雜度：$O(\log n)$，其中 $n$ 是數組 $\text{nums}$ 的長度。排序需要 $O(\log n)$ 的遞歸調用棧空間。

解法二

思路和算法

由于計算最大乘積只需要得到數組中最大的三個元素與最小的兩個元素，并不需要得到所有元素的順序，因此可以直接遍歷數組找到最大的兩個元素。

遍歷數組 $\text{nums}$，遍歷過程中維護最大的三個元素與最小的兩個元素，對于每個元素 $\text{num}$，與最大的三個元素以及最小的兩個元素比較，并更新相應的元素值。遍歷結束之后，即可得到最大的三個元素與最小的兩個元素，并計算最大乘積。

代碼

class Solution {public int maximumProduct(int[] nums) {int firstMax = Integer.MIN_VALUE, secondMax = Integer.MIN_VALUE, thirdMax = Integer.MIN_VALUE;int firstMin = Integer.MAX_VALUE, secondMin = Integer.MAX_VALUE;for (int num : nums) {if (num > firstMax) {thirdMax = secondMax;secondMax = firstMax;firstMax = num;} else if (num > secondMax) {thirdMax = secondMax;secondMax = num;} else if (num > thirdMax) {thirdMax = num;}if (num < firstMin) {secondMin = firstMin;firstMin = num;} else if (num < secondMin) {secondMin = num;}}return Math.max(thirdMax * secondMax * firstMax, firstMin * secondMin * firstMax);}
}

復雜度分析

• 時間復雜度：$O(n)$，其中 $n$ 是數組 $\text{nums}$ 的長度。需要遍歷數組一次。

• 空間復雜度：$O(1)$。