LeetCode.628.Maximum Product of Three Numbers 数组中三个数的最大乘积

题目描述

628 Maximum Product of Three Numbers
https://leetcode-cn.com/problems/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.

---

解题过程

相似题目
LeetCode.628.Maximum Product of Three Numbers 数组中三个数的最大乘积
LeetCode.414.Third Maximum Number 数组中第三大的数

不会做，有个模糊的先排序的思路，但没想清楚，看题解才会。
将数组升序排序后，最大三个数的成绩只可能是
max(最大三个正数的成绩，两个最小的负数和最大正数的乘积)
所以我们只需要在一次遍历中，求出这5个数即可。

时间复杂度 O(n) 空间复杂度 O(1)

private static class SolutionV2020 {
    public int maximumProduct(int[] nums) {
        // 最大值，次大值，3大值
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        // 最小值、次小值
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max1) {
                max3 = max2;
                max2 = max1;
                max1 = nums[i];
            } else if (nums[i] > max2) {
                max3 = max2;
                max2 = nums[i];
            } else if (nums[i] > max3) {
                max3 = nums[i];
            }
            if (nums[i] < min1) {
                min2 = min1;
                min1 = nums[i];
            } else if (nums[i] < min2) {
                min2 = nums[i];
            }
        }
        return Math.max(max1 * max2 * max3, min1 * min2 * max1);
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_628_MaximumProductOfThreeNumbers.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_628_MaximumProductOfThreeNumbers.java

---