628. 三个数的最大乘积

  1. class Solution {
  2.     public int maximumProduct(int[] nums) {
  3.         Arrays.sort(nums);
  4.         int n = nums.length;
  5.         return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 3] * nums[n - 2] * nums[n - 1]);
  6.     }
  8. // 作者：LeetCode-Solution
  9. // 链接：https://leetcode-cn.com/problems/maximum-product-of-three-numbers/solution/san-ge-shu-de-zui-da-cheng-ji-by-leetcod-t9sb/
  10. }

复杂度分析
时间复杂度：O(NlogN)，其中 N 为数组长度。排序需要 O(NlogN) 的时间。
空间复杂度：O(logN)，主要为排序的空间开销。

排序

首先将数组排序。
如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积；如果全是非正数，则最大的三个数相乘同样也为最大乘积。
如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对值最大）与最大正数的乘积。
综上，我们在给数组排序后，分别求出三个最大正数的乘积，以及两个最小负数与最大正数的乘积，二者之间的最大值即为所求答案.

  1.     public int maximumProduct(int[] nums) {
  2.         // 最小的和第二小的
  3.         int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
  4.         // 最大的、第二大的和第三大的
  5.         int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
  7.         for (int x : nums) {
  8.             if (x < min1) {
  9.                 min2 = min1;
  10.                 min1 = x;
  11.             } else if (x < min2) {
  12.                 min2 = x;
  13.             }
  15.             if (x > max1) {
  16.                 max3 = max2;
  17.                 max2 = max1;
  18.                 max1 = x;
  19.             } else if (x > max2) {
  20.                 max3 = max2;
  21.                 max2 = x;
  22.             } else if (x > max3) {
  23.                 max3 = x;
  24.             }
  25.         }
  27.         return Math.max(min1 * min2 * max1, max1 * max2 * max3);
  28.     }
  30. 作者：LeetCode-Solution
  31. 链接：https://leetcode-cn.com/problems/maximum-product-of-three-numbers/solution/san-ge-shu-de-zui-da-cheng-ji-by-leetcod-t9sb/

线性扫描

实际上只要求出数组中最大的三个数以及最小的两个数，因此我们可以不用排序，用线性扫描直接得出这五个数。

复杂度分析

  • 时间复杂度：O(N)O(N)，其中 NN 为数组长度。我们仅需遍历数组一次。
  • 空间复杂度：O(1)O(1)。