628-maximum-product-of-three-numbers.md

628. Maximum Product of Three Numbers - 三个数的最大乘积

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

示例 1:

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

示例 2:

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

注意:

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

---

题目标签：Array / Math

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
java	5 ms	40.7 MB

class Solution {
    public int maximumProduct(int[] nums) {
        int m1 = Integer.MIN_VALUE, m2 = Integer.MIN_VALUE, m3 = Integer.MIN_VALUE, m4 = 0, m5 = 0;
        for (int a : nums) {
            if (a > m3) {
                if (a > m2) {
                    if (a > m1) {
                        m3 = m2;
                        m2 = m1;
                        m1 = a;
                    } else {
                        m3 = m2;
                        m2 = a;
                    }
                } else {
                    m3 = a;
                }
            }
            if (a < 0) {
                if (a < m5) {
                    if (a < m4) {
                        m5 = m4;
                        m4 = a;
                    } else {
                        m5 = a;
                    }
                }
            }
        }
        return Math.max(m1 * m2 * m3, m4 * m5 * m1);
    }
}

Language	Runtime	Memory
python3	100 ms	N/A

import heapq

class Solution:
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        a = heapq.nlargest(3, nums)
        b = heapq.nsmallest(3, nums)
        return max(a[0] * a[1] * a[2], a[0] * b[0] * b[1])