5191614317615_.pic_hd.jpg
题目描述
leetcode 第628题：三个数的最大乘积
给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
示例：
输入：nums = [-100,-2,-3,1]
输出：300
解题方法
排序
参照题解
- 解题思路
将数组由小到大排序
求数组中三个最大数的乘积
求数组中两个最小数和一个最大数的乘积
最后求得三个数的最大乘积
- 复杂度
时间复杂度：O(nlogn)，n为数组长度
空间复杂度：O(logn)
- 代码实现
python3
class Solution:
def maximumProduct(self, nums: List[int]) -> int:
nums.sort()
return max(nums[-1]*nums[-2]*nums[-3],nums[0]*nums[1]*nums[-1])
php
class Solution {
function maximumProduct($nums) {
$n = count($nums);
asort($nums);
$nums = array_values($nums);
return max($nums[$n-1]*$nums[$n-2]*$nums[$n-3],$nums[0]*$nums[1]*$nums[$n-1]);
}
}
- 文字草稿
nums = [-100,-2,-3,1]
正序排列后得到[-100,-3,-2,1]
最大三个最大数的乘积为6=(-3)(-2)1
两个最小数和一个最大数的乘积为300=(-100)(-3)1
三个数的最大乘积即为300
