原题链接：Leetcode 628. Maximum Product of Three Numbers
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
题目大意：
给一个数组，要求返回数组任意三个数的乘积中最大的那个
方法一：排序
思路：
首先要明确的一点就是，数组里面的元素有正有负，那么大致可以分为：
- 所有元素均正，这时候答案就是最大的三个元素相乘
- 所有元素均负，这时候答案也是最大的三个元素相乘
- 有正有负情况，答案也可能是最大三个正数相乘，也可能是两个最小负数再乘一个最大正数
综合以上三种情况，结果就是 max（三个最大元素相乘，两个最小元素与最大元素相乘）文章来源：https://www.toymoban.com/news/detail-811575.html
C++实现：
class Solution {
public:
int maximumProduct(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
// 最大的三个数 与 最小的2个数与最大的数相乘 中较大的那个
return max(nums[n - 1] * nums[n - 2] * nums[n - 3], nums[0] * nums[1] * nums[n - 1]);
}
};
复杂度分析：
- 时间复杂度：O(nlogn)，花费在
sort()上 - 空间复杂度：O(1)
补充：
用sort()实现从大到小排序：文章来源地址https://www.toymoban.com/news/detail-811575.html
方法一：
sort(nums.begin(), nums.end(), greater<int>());
方法二：写cmp规则
bool cmp(int x,int y){
return x > y;
}
sort(nums.begin(), nums.end(), cmp);
到了这里，关于Leetcode 628. 三个数的最大乘积的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
