【LeetCode_数组_遍历】628. 三个数的最大乘积

原题链接：628. 三个数的最大乘积

题目概述

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

输入：nums = [1,2,3]
输出：6
1
2

提示：

3 <= nums.length <= 104
-1000 <= nums[i] <= 1000

2022年11月14日10:22:23

思路一：排序后在取值

这道题目还是蛮有意思的，很容易出错。

1. 如果数组里面全部为非负数或者非正数，最大的乘积 即 排序后最大的三个数的乘积
   nums = [1,2,3]，[-5,-4,-3,-2,-1]，[-8,-4,-1,0]
2. 如果数组里面有负数和正数，最大的乘积
   • 排序后第0位和第1位和最后1位的乘积
     nums = [ -1000, -100, 0, 2, 345]
   • 排序后最大的三个数的乘积
     nums = [ -1000, -100, 0, 2, 345, 2345, 345564]

class Solution {
    public int maximumProduct(int[] nums) {
        // 1. 排序
        Arrays.sort(nums);
        // 2. 排序完了
        // 如果数组里面全部为非负数或者非正数，最大的乘积 即 排序后最大的三个数的乘积
        // 如果数组里面有负数和正数，最大的乘积 ①排序后第0位和第1位和最后1位的乘积 ②排序后最大的三个数的乘积
        int n = nums.length;
        return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 1] * nums[n - 2] * nums[n - 3]);
    }
}
1
2
3
4
5
6
7
8
9
10
11

思路二：一次遍历找出3个最大的数和2个最小的数

这里的5个数的初始值容易混乱。

class Solution {
    public int maximumProduct(int[] nums) {
        /**
         * 最小的和第二小的  231-1.
         */
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        /**
         * 最大的、第二大的和第三大的  -231.
         */
        int max1 = Integer.MIN_VALUE,max2 = Integer.MIN_VALUE ,max3 = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }


            if (num > max1) {
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max3 = max2;
                max2 = num;
            } else if (num > max3) {
                max3 = num;
            }
        }
        return Math.max(max1 * max2 * max3, min1 * min2 * max1);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34