[LeetCode] 628. Maximum Product of Three Numbers

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

Input: [1,2,3]

Output: 6

Example 2:

Input: [1,2,3,4]

Output: 24

Note:

The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

这个题目就是需要注意负数的情况即可, 我们如果用排序的话, 比较max(nums[0]*nums[1]*nums[-1], nums[-1]*nums[-2]*nums[-3])即可. T: O(nlgn)

要T: O(n) 的话就需要得到min1, min2, max1, max2, max3同理比较max(min1 * min2 * max1, max1 * max2 * max3)即可.

Code

1) T: O(nlgn)

class Solution:

    def maxProduct3nums(self, nums):

        nums.sort()

        return max(nums[0]*nums[1]*nums[-1], nums[-1]*nums[-2]*nums[-3])

2) T: O(n)

class Solution:

    def maxProduct3nums(self, nums):

        ans = [1001]*2 + [-1001]*3  # min1, min2, max1, max2, max3

        for num in nums:

            if num > ans[-1]:

                ans[-1], ans[-2], ans[-3] = num, ans[-1], ans[-2]

            elif num > ans[-2]:

                ans[-2], ans[-3] = num, ans[-2]

            elif num > ans[-3]:

                ans[-3] = num

            if num < ans[0]:

                ans[0], ans[1] = num, ans[0]

            elif num < ans[1]:

                ans[1] = num

        return max(ans[0]*ans[1]*ans[-1], ans[-1]*ans[-2]*ans[-3])

巴特西

[LeetCode] 628. Maximum Product of Three Numbers_Easy

最新文章

热门文章