难度: Easy
给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例 1：
输入：nums = [1,2,3] 输出：6
示例 2：
输入：nums = [1,2,3,4] 输出：24
示例 3：
输入：nums = [-1,-2,-3] 输出：-6
提示：
3 <= nums.length <= 104-1000 <= nums[i] <= 1000
Submission
运行时间: 35 ms
内存: 16.9 MB
class Solution:
def maximumProduct(self, nums: List[int]) -> int:
max_1 = max_2 = max_3 = -inf
min_1 = min_2 = inf
for elem in nums:
if elem > max_3:
max_3 = elem
max_1, max_2, max_3 = self.sort_max(max_1, max_2, max_3)
if elem < min_2:
min_2 = elem
min_1, min_2 = self.sort_min(min_1, min_2)
return max(max_1 * max_2 * max_3, max_1 * min_1 * min_2)
def sort_max(self, max_1, max_2, max_3):
if max_1 < max_2:
max_1, max_2 = max_2, max_1
if max_1 < max_3:
max_1, max_3 = max_3, max_1
if max_2 < max_3:
max_2, max_3 = max_3, max_2
return max_1, max_2, max_3
def sort_min(self, min_1, min_2):
if min_1 > min_2:
min_1, min_2 = min_2, min_1
return min_1, min_2
Explain
该题解的思路是在数组中维护最大的三个数和最小的两个数。遍历数组，对于每个元素，检查它是否比当前最大的三个数中的任意一个更大，或者比当前最小的两个数中的任意一个更小。如果满足条件，就更新对应的最大数或最小数，并保持它们按照大小顺序排列。最后，返回最大的三个数的乘积与最大数与最小的两个数的乘积中的较大值。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def maximumProduct(self, nums: List[int]) -> int:
# 初始化最大的三个数和最小的两个数
max_1 = max_2 = max_3 = -inf
min_1 = min_2 = inf
for elem in nums:
# 如果当前元素大于最大的三个数中的任意一个
if elem > max_3:
max_3 = elem
# 更新最大的三个数，并保持它们按照大小顺序排列
max_1, max_2, max_3 = self.sort_max(max_1, max_2, max_3)
# 如果当前元素小于最小的两个数中的任意一个
if elem < min_2:
min_2 = elem
# 更新最小的两个数，并保持它们按照大小顺序排列
min_1, min_2 = self.sort_min(min_1, min_2)
# 返回最大的三个数的乘积与最大数与最小的两个数的乘积中的较大值
return max(max_1 * max_2 * max_3, max_1 * min_1 * min_2)
def sort_max(self, max_1, max_2, max_3):
# 对最大的三个数进行排序
if max_1 < max_2:
max_1, max_2 = max_2, max_1
if max_1 < max_3:
max_1, max_3 = max_3, max_1
if max_2 < max_3:
max_2, max_3 = max_3, max_2
return max_1, max_2, max_3
def sort_min(self, min_1, min_2):
# 对最小的两个数进行排序
if min_1 > min_2:
min_1, min_2 = min_2, min_1
return min_1, min_2
Explore
在更新最大或最小值时，代码通过使用条件判断和适当的排序方法来确保不会覆盖掉其它重要值。例如，当发现一个新的最大值时，不是简单地替换当前最大值，而是将新值放入适当位置，并将其他值按顺序下移。这种方法确保了在更新任一值时，其他重要的值仍被保存并适当地调整位置。
在比较前维护序列的顺序可能会导致更多的计算，因为每次插入新的值都可能需要比较和移动。而在更新后排序可以减少操作的次数，因为只有在值确实需要更新时才进行排序。这种方法提高了效率，尤其是在大多数情况下新遍历的值并不会成为新的最大或最小值时更为明显。
是的，`sort_max`和`sort_min`函数中的比较和交换可能会导致不必要的操作。如果数值没有发生改变（即新插入的值并未改变排序后的序列），这些函数仍会执行比较和可能的交换操作。这可能导致额外的计算开销，尽管这种情况在大多数情况下对性能的影响较小。
在这种情况下，代码需要确保任何元素的更新都独立处理，并检查对最大值和最小值的潜在影响。例如，如果一个新元素可能是新的最小值也可能是新的最大值，代码首先在最小值数组进行更新和排序，然后再处理最大值数组。这种方法确保了更新的正确性和数据的完整性，避免了因处理顺序错误而导致的潜在遗漏。