给定一个无序数组包含正数、负数和0要求从中找到3个数的乘积使得乘积最大并且时间复杂度为On空间复杂度为O1。 输入描述：无序整数数组an 输出描述：满足条件的最大乘积。 输出样例： 4 3 4 1 2 输出： 24

思路：

• 首先对数组进行排序，时间复杂度为O(nlogn)。

• 如果数组中全是非负数或全是非正数，那么最大乘积为数组中最后三个数的乘积或最前三个数的乘积，因为排序后最后三个数全是非负数，最前三个数全是非正数。

• 如果数组中既有正数又有负数，那么最大乘积只可能由以下两种情况中的一种得到：

• 最后三个数的乘积：数组中最后三个数全是非负数或只有一个负数。

• 前两个数和最后一个数的乘积：数组中最前两个数为负数，最后一个数为非负数。

这是因为数组中只有这两种情况下，三个数的乘积才可能最大。

代码实现：

时间复杂度：O(nlogn)，空间复杂度：O(1)。

C++ 代码

class Solution { public: int maximumProduct(vector& nums) { sort(nums.begin(), nums.end()); // 排序 int n = nums.size(); return max(nums[n-1]*nums[n-2]*nums[n-3], nums[0]*nums[1]*nums[n-1]); // 返回最大乘积 } };

Python 代码

class Solution: def maximumProduct(self, nums: List[int]) -> int: nums.sort() # 排序 n = len(nums) return max(nums[n-1]*nums[n-2]*nums[n-3], nums[0]*nums[1]*nums[n-1]) # 返回最大乘