[每日 LeetCode] 628. Maximum Product of Three Numbers

Description:

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:

1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
2. Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

思路：本题要求数组中三个元素乘积的最大值。最开始想到直接对数组排序，取最大三个元素相乘即可，结果被无情打脸，没有考虑负数和 0 的情况。总结了一下，可能取得最大值要么是三个最大值相乘，要么是一个最大值和两个最小值相乘，最后取两者的最大值即可。

C++ 代码

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(),nums.end());
        int max1 = nums[n-1], max2 = nums[n-2], max3 = nums[n-3];
        int min1 = nums[0], min2 = nums[1];
        return max(max1*max2*max3, max1*min1*min2);
    }
};

运行时间：68ms

运行内存：10.8M