极值乘积的智慧：力扣628题"三个数的最大乘积"的多种解法与深度解析

一、问题描述

给定一个整数数组 nums，找出三个数使得它们的乘积最大，并返回这个最大乘积。数组中可能包含正数、负数和零。

示例：

输入：nums = [1,2,3]

输出：6

输入：nums = [-1,-2,-3]

输出：-6

二、解题思路

要找到三个数的最大乘积，需要考虑两种情况：

1. 三个最大的正数的乘积

2. 两个最小的负数和一个最大的正数的乘积（负负得正）

最优解需要同时考虑这两种情况，然后取较大值。

三、完整代码

#include <vector>
#include <algorithm>
using namespACe std;

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        // 先对数组进行排序
        sort(nums.begin(), nums.end());
        int n = nums.size();
        
        // 计算两种可能的情况
        int case1 = nums[n-1] * nums[n-2] * nums[n-3]; // 三个最大正数
        int case2 = nums[0] * nums[1] * nums[n-1];     // 两个最小负数和一个最大正数
        
        // 返回两种情况中的较大值
        return max(case1, case2);
    }
};

四、算法详解

1. 关键思路

• 排序后数组的最大乘积只可能出现在两种情况下

• 需要考虑负数相乘变正数的情况

• 不需要考虑所有组合，只需关注极值

2. 优化思路

1. ‌线性扫描法‌：可以不用排序，直接找出最大的三个数和最小的两个数

2. ‌边界处理‌：处理数组长度小于3的特殊情况

3. ‌整数溢出‌：考虑使用long类型处理大数相乘

3. 复杂度分析

• 排序解法：时间复杂度O(nlogn)，空间复杂度O(1)

• 线性扫描法：时间复杂度O(n)，空间复杂度O(1)

五、关键点解析

1. 负数处理

• 两个负数相乘得正数

• 负数的绝对值越大，乘积越大

• 需要考虑负数和正数的组合情况

2. 边界条件

• 数组长度恰好为3的情况

• 数组中全为正数或全为负数的情况

• 包含0的情况

3. 最优解证明

• 数学上可以证明最大乘积只可能出现在这两种情况

• 其他组合要么乘积更小，要么是这两种情况的子集