【每日一题】 628. 三个数的最大乘积

迈不过友情╰ 2023-01-08 12:22 179阅读 0赞

# 【每日一题】 628. 三个数的最大乘积 #

> 避免每日太过咸鱼，一天搞定一道LeetCode算法题

## 一、题目描述 ##

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

**提示：**

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

**示例 1：**

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

**示例 2：**

输入: [1,2,-3,4]
    输出: 8

## 二、题解 ##

### 1. 解法 ###

**解题思路：**

这道题是为了得到由三位数乘积的最大值，其实也就两种情况，第一种是直接找到最大的三位大于零的数相乘得到的 值，第二种是两位最小的负数和最大的正数乘积。

public static int maximumProduct(int[] nums) { 
            Arrays.sort(nums);
            int n = nums.length;
            return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 3] * nums[n - 2] * nums[n - 1]);
        }

**复杂度分析**

*  时间复杂度：O(Nlog N)，其中 N 为数组长度。排序需要 O(Nlog N) 的时间。
 *  空间复杂度：O(logN)，主要为排序的空间开销。

所以这种方式主要的开销都在于 Arrays.sort(nums); 这里。

所以还有一种方式，就是直接遍历一遍数组，取出里面最大的三位正整数，和最小的两位数就行了。

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

**复杂度分析**

*  时间复杂度：O(N)*O*(*N*)，其中 N*N* 为数组长度。我们仅需遍历数组一次。
 *  空间复杂度：O(1)*O*(1)。

题目来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/distance-between-bus-stops

\--------------最后感谢大家的阅读，愿大家技术越来越流弊！--------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]

\--------------也希望大家给我点支持，谢谢各位大佬了！！！--------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]: /images/20221119/712d8990ef2a479d9b516a7762af59cc.png