mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
39 lines
1.6 KiB
Markdown
39 lines
1.6 KiB
Markdown
# [628. Maximum Product of Three Numbers](https://leetcode.com/problems/maximum-product-of-three-numbers/description/)
|
||
# 思路
|
||
这题由于可能存在负数和0，所以当数组元素个数大于3时需要分情况仔细考虑：
|
||
* (1. 全是非正数，则选三个最大的数相乘即可；
|
||
* (2. 只有一个正数，用这个(最大的)正数乘以最小的两个数(肯定是非正数)即可；
|
||
* (3. 有2个正数，选最大的(正)数与最小的两个(非正)数相乘；
|
||
* (4. 有3个及以上的正数，选三个最大的数相乘。
|
||
|
||
综上，这三个数要么是三个最大的数(1、4)，要么是一个最大的数与两个最小的数(2、3)。
|
||
所以找出最大的三个数与最小的两个数，然后再比较两种乘积的大小即可。
|
||
时间复杂度O(n)
|
||
# C++
|
||
```C++
|
||
class Solution {
|
||
public:
|
||
int maximumProduct(vector<int>& nums) {
|
||
// if(nums.size() == 3) return nums[0] * nums[1] * nums[2];
|
||
int mx1 = INT_MIN, mx2 = INT_MIN, mx3 = INT_MIN;
|
||
int mn1 = INT_MAX, mn2 = INT_MAX;
|
||
for (int num : nums) { // 注意这种用一次循环求最大三个数的方式
|
||
if (num > mx1) {
|
||
mx3 = mx2; mx2 = mx1; mx1 = num;
|
||
} else if (num > mx2) {
|
||
mx3 = mx2; mx2 = num;
|
||
} else if (num > mx3) {
|
||
mx3 = num;
|
||
}
|
||
|
||
if (num < mn1) {
|
||
mn2 = mn1; mn1 = num;
|
||
} else if (num < mn2) {
|
||
mn2 = num;
|
||
}
|
||
}
|
||
return max(mx1 * mx2 * mx3, mx1 * mn1 * mn2);
|
||
}
|
||
};
|
||
```
|