Question

628. Maximum Product of Three Numbers

中文文档

Description

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

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

• 3 <= nums.length <= 104
• -1000 <= nums[i] <= 1000

Solutions

Solution 1

class Solution:
  def maximumProduct(self, nums: List[int]) -> int:
    nums.sort()
    a = nums[-1] * nums[-2] * nums[-3]
    b = nums[-1] * nums[0] * nums[1]
    return max(a, b)

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

class Solution {
public:
  int maximumProduct(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int a = nums[n - 1] * nums[n - 2] * nums[n - 3];
    int b = nums[n - 1] * nums[0] * nums[1];
    return max(a, b);
  }
};

func maximumProduct(nums []int) int {
  sort.Ints(nums)
  n := len(nums)
  a := nums[n-1] * nums[n-2] * nums[n-3]
  b := nums[n-1] * nums[0] * nums[1]
  if a > b {
    return a
  }
  return b
}

function maximumProduct(nums: number[]): number {
  nums.sort((a, b) => a - b);
  const n = nums.length;
  const a = nums[n - 1] * nums[n - 2] * nums[n - 3];
  const b = nums[n - 1] * nums[0] * nums[1];
  return Math.max(a, b);
}

Solution 2

class Solution:
  def maximumProduct(self, nums: List[int]) -> int:
    top3 = nlargest(3, nums)
    bottom2 = nlargest(2, nums, key=lambda x: -x)
    return max(top3[0] * top3[1] * top3[2], top3[0] * bottom2[0] * bottom2[1])

class Solution {
  public int maximumProduct(int[] nums) {
    final int inf = 1 << 30;
    int mi1 = inf, mi2 = inf;
    int mx1 = -inf, mx2 = -inf, mx3 = -inf;
    for (int x : nums) {
      if (x < mi1) {
        mi2 = mi1;
        mi1 = x;
      } else if (x < mi2) {
        mi2 = x;
      }
      if (x > mx1) {
        mx3 = mx2;
        mx2 = mx1;
        mx1 = x;
      } else if (x > mx2) {
        mx3 = mx2;
        mx2 = x;
      } else if (x > mx3) {
        mx3 = x;
      }
    }
    return Math.max(mi1 * mi2 * mx1, mx1 * mx2 * mx3);
  }
}

class Solution {
public:
  int maximumProduct(vector<int>& nums) {
    const int inf = 1 << 30;
    int mi1 = inf, mi2 = inf;
    int mx1 = -inf, mx2 = -inf, mx3 = -inf;
    for (int x : nums) {
      if (x < mi1) {
        mi2 = mi1;
        mi1 = x;
      } else if (x < mi2) {
        mi2 = x;
      }
      if (x > mx1) {
        mx3 = mx2;
        mx2 = mx1;
        mx1 = x;
      } else if (x > mx2) {
        mx3 = mx2;
        mx2 = x;
      } else if (x > mx3) {
        mx3 = x;
      }
    }
    return max(mi1 * mi2 * mx1, mx1 * mx2 * mx3);
  }
};

func maximumProduct(nums []int) int {
  const inf = 1 << 30
  mi1, mi2 := inf, inf
  mx1, mx2, mx3 := -inf, -inf, -inf
  for _, x := range nums {
    if x < mi1 {
      mi1, mi2 = x, mi1
    } else if x < mi2 {
      mi2 = x
    }
    if x > mx1 {
      mx1, mx2, mx3 = x, mx1, mx2
    } else if x > mx2 {
      mx2, mx3 = x, mx2
    } else if x > mx3 {
      mx3 = x
    }
  }
  return max(mi1*mi2*mx1, mx1*mx2*mx3)
}

function maximumProduct(nums: number[]): number {
  const inf = 1 << 30;
  let mi1 = inf,
    mi2 = inf;
  let mx1 = -inf,
    mx2 = -inf,
    mx3 = -inf;
  for (const x of nums) {
    if (x < mi1) {
      mi2 = mi1;
      mi1 = x;
    } else if (x < mi2) {
      mi2 = x;
    }
    if (x > mx1) {
      mx3 = mx2;
      mx2 = mx1;
      mx1 = x;
    } else if (x > mx2) {
      mx3 = mx2;
      mx2 = x;
    } else if (x > mx3) {
      mx3 = x;
    }
  }
  return Math.max(mi1 * mi2 * mx1, mx1 * mx2 * mx3);
}