leetcode：628. 三个数的最大乘积

题目

给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例：

  1. 输入：nums = [1,2,3]
  2. 输出：6
  1. 输入：nums = [1,2,3,4]
  2. 输出：24
  1. 输入：nums = [-1,-2,-3]
  2. 输出：-6

解答 & 代码

三个数的最大乘积，要么是三个最大的正数的乘积，要么是两个最小的负数和最大正数的乘积，比较两种情况即可。
可以给数组排序，也可以直接遍历查找最大的三个数及最小的两个数

  1. class Solution {
  2. public:
  3.     int maximumProduct(vector<int>& nums) {
  4.         int len = nums.size();
  5.         sort(nums.begin(), nums.end());
  6.         // 三个数的最大乘积，要么是三个最大的正数的乘积，要么是两个最小的负数和最大正数的乘积，
  7.         // 比较两种情况即可
  8.         int candidate1 = nums[len - 1] * nums[len - 2] * nums[len - 3];
  9.         int candidate2 = nums[len - 1] * nums[0] * nums[1];
  10.         return max(candidate1, candidate2);
  11.     }
  12. };

复杂度分析：设数组长为 N

  • 时间复杂度 O(N logN)：排序的时间复杂度。如果不排序直接遍历查找的时间复杂度为 O(N)
  • 空间复杂度 O(1)

执行结果：

  1. 执行结果：通过
  3. 执行用时：36 ms, 在所有 C++ 提交中击败了 78.37% 的用户
  4. 内存消耗：27 MB, 在所有 C++ 提交中击败了 62.02% 的用户