【C++刷题】力扣-#628-三个数的最大乘积

题目形貌

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

示例 1

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

复制代码

示例 2

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

复制代码

示例 3

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

复制代码

题解

这个题目可以通过排序和考虑正数与负数的组合来办理。

• 排序：起首对数组进行排序。
  
• 考虑环境：
  ○ 如果数组中包含负数，最大的乘积可能来自两个最小的负数（它们的乘积为正数）和一个最大的正数。
  ○ 如果数组中不包含负数，最大的乘积就是最大的三个数的乘积。
  
• 盘算最大乘积：根据排序后的数组，盘算上述两种环境的乘积，并返回较大的那个。
  

代码实现

1. int maximumProduct(vector<int>& nums) {
2.     sort(nums.begin(), nums.end());
3.     int n = nums.size();
4.     // 情况1: 两个最小的负数和一个最大的正数
5.     int product1 = nums[0] * nums[1] * nums[n - 1];
6.     // 情况2: 三个最大的正数
7.     int product2 = nums[n - 1] * nums[n - 2] * nums[n - 3];
9.     return max(product1, product2);
10. }

复制代码

复杂度分析

● 时间复杂度：O(n log n)，其中 n 是数组 nums 的长度。主要时间斲丧在排序上。
● 空间复杂度：O(1)，除了输入数组外，我们只使用了常数个额外变量。
这个算法通过排序和考虑两种可能的环境来盘算最大乘积。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。