三个数的最大乘积

三个数的最大乘积_牛客题霸_牛客网

问题简述

给定一个长度为 nn 的无序数组 AA ，包含正数、负数和 0 ，请从中找出 3 个数，使得乘积最大，返回这个乘积。

要求时间复杂度： O(n) ，空间复杂度： O(1) 。

思路1：排序

• 设倒序排序后的数组为 A；

• 最大乘积只有两种可能：max(A[0]*A[1]*A[2], A[-1]*A[-2]*A[0])；

Python

class Solution:
    def solve(self , A: List[int]) -> int:
        A.sort(reverse=True)
        r1 = A[0] * A[1] * A[2]
        r2 = A[-1] * A[-2] * A[0]
        return max(r1, r2)

思路2：堆

• 确定了最大乘积的可能；

• 我们实际上要找到 5 个数：最大的 3 个数和 最小的 2 个数；可以利用堆结构；

• 时间复杂度 O(N)；

Python

class Solution:
    def solve(self , A: List[int]) -> int:
        
        import heapq
        
        mx = []  # 小顶堆，保存最大的 3 个数
        for i in range(len(A)):
            if i >= 3:
                heapq.heappushpop(mx, A[i])  # pushpop 操作不会改变堆中元素的数量
            else:
                heapq.heappush(mx, A[i])

        mi = []  # 大顶堆，保存最小的 2 个数
        for i in range(len(A)):
            if i >= 2:
                heapq.heappushpop(mi, -A[i])
            else:
                heapq.heappush(mi, -A[i])
        
        r1 = mx[0] * mx[1] * mx[2]
        r2 = mi[0] * mi[1] * max(mx)  # 因为堆不保证整体有序，所以不确定最大的数在 mx 中哪个位置
        return max(r1, r2)