首页 leetcode

628. 三个数的最大乘积

题目描述

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

注意:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-product-of-three-numbers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

输入样例:

[1,2,3]

[1,2,3,4]

输出样例:

6

24

ac代码

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

心得:

第一次WA:没有考虑到负数,忘记两个负数相乘位正数。

第二次AC:考虑到了负数的情况,写出了解放。

官方方法:

线性扫描(如何查找多个最值)

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        // 最小的和第二小的
        int min1 = INT_MAX, min2 = INT_MAX;
        // 最大的、第二大的和第三大的
        int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;

        for (int x: nums) {
            //min1是最小的
            if (x < min1) {
                min2 = min1;
                min1 = x;
                //min2是比min1大,但比min2小的
            } 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 max(min1 * min2 * max1, max1 * max2 * max3);
    }
};

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/maximum-product-of-three-numbers/solution/san-ge-shu-de-zui-da-cheng-ji-by-leetcod-t9sb/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



文章评论

目录