当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.628.Maximum Product of Three Numbers 数组中三个数的最大乘积

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


上一篇 LeetCode.121.Best Time to Buy and Sell Stock 买卖股票的最佳时机

下一篇 LeetCode.152.Maximum Product Subarray 最大连续子序列积

阅读
评论
359
阅读预计2分钟
创建日期 2020-02-05
修改日期 2020-02-05
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论