题解 | #三个数的最大乘积#

维护5个变量，即第一最大数(m1)、第二最大数(m2)、第三最大数(m3)、最小数(min1)、倒数第二小数(min2)。

当数组A中为全正数或者全负数，结果为 m1 * m2 * m3 即绝对值最大的正数或绝对值最小的负数。 当数组中有正有负，则可能为 m1 * m2 * m3 或 min1 * min2 * m1。取两者大值。
总之 无论如何返回:

max((m1 * m2 * m3),  (min1 * min2 * m1))

注意，如果严格按要求，则本题不可使用排序算法。因为题目要求时间复杂度O(n)，没有排序算法可以保证O(n)复杂度

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最大乘积
# @param A int整型一维数组 
# @return long长整型
#
class Solution:
    def solve(self , A):
        # write code here
        lListLarge = [-100000,-100000,-100000]
        lListSmall = [100000,100000]
        for i in A:
            if i >= lListLarge[-1]:
                lListLarge[-1] = i
                self.BubbleUP(lListLarge)
            if i <= lListSmall[-1]:
                lListSmall[-1] = i
                self.BubbleDown(lListSmall)
        iRes1 = lListLarge[0] * lListLarge[1] * lListLarge[2]
        iRes2 = lListSmall[0] * lListSmall[1] * lListLarge[0]
        return max(iRes1, iRes2)
        
    def BubbleDown(self, lList): # update small Arr
        for i in range(len(lList) - 1, 0, -1):
            if lList[i] <= lList[i - 1]:
                iTemp = lList[i]
                lList[i] = lList[i - 1]
                lList[i - 1] = iTemp
            else:
                break
                
    def BubbleUP(self, lList): # update small Arr
        for i in range(len(lList) - 1, 0, -1):
            if lList[i] >= lList[i - 1]:
                iTemp = lList[i]
                lList[i] = lList[i - 1]
                lList[i - 1] = iTemp
            else:
                break