LeetCode 628. 三个数的最大乘积 Maximum P

【题目描述】
给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

【示例1】

输入: [1,2,3]
输出: 6

【示例2】

输入: [1,2,3,4]
输出: 24

【注意】

1、给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
2、输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。

【思路1】
1、排序
2、假如数组只有三个元素，直接返回三个元素乘积
3、如果有负数，那么最小的两个负数和最大的一个正数相乘 最大乘积
4、都是正数 返回最大三个数相乘
5、时间复杂度O(nlogn)
6、空间复杂度0(1)

Swift代码实现：

func maximumProduct(_ nums: [Int]) -> Int {
    if nums.count == 3 {
        return nums[0]*nums[1]*nums[2]
    }
    var tmp = nums.sorted()
    var m = Int.min
    if  tmp[tmp.count-3] >= 0 && tmp[tmp.count-2] >= 0 && tmp[tmp.count-1] >= 0 {
        m = max(m, tmp[tmp.count-3] * tmp[tmp.count-2] * tmp[tmp.count-1])
    }
    if tmp.first! <= 0 && tmp[tmp.count-1] >= 0 && tmp[tmp.count-2] >= 0 {
        m = max(m, tmp.first!*tmp[tmp.count-1]*tmp[tmp.count-2])
    }
    if tmp[0] <= 0 && tmp[1] <= 0 && tmp[tmp.count-1] >= 0 {
        m = max(m, tmp[0]*tmp[1]*tmp[tmp.count-1])
    }
    return m
}

【思路2】
1、三个指针分别指向第一大maxF，第二大maxS，第三大maxT
2、另外两个指针分别指向最小min1,min2（检测负数）
3、最后返回max(maxFmaxSmaxT,min1min2maxF)
4、时间复杂度O(n)
5、空间复杂度O(1)

Swift代码实现：

func maximumProduct(_ nums: [Int]) -> Int {
    if nums.count == 3 {
        return nums[0]*nums[1]*nums[2]
    }
    var min1 = 0,min2 = 0
    var maxFir = Int.min,maxSec = Int.min,maxThird = Int.min
    for n in nums {
        if n > maxFir {
            maxThird = maxSec
            maxSec = maxFir
            maxFir = n
        } else if n > maxSec {
            maxThird = maxSec
            maxSec = n
        } else if n > maxThird {
            maxThird = n
        }
        if n < min1 {//保留最小的两个数（负数）
            min2 = min1
            min1 = n
        } else if n < min2 {
            min2 = n
        }
    }
    return max(maxFir*maxSec*maxThird, min1*min2*maxFir)
}

后续会继续更新文章，也可以关注我的公众号，基本每日一题🙂：

个人公号.jpg