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

  |   0 评论   |   475 浏览

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

评论

发表评论