Medium
题目描述
给你一个整数数组 nums。
你必须将数组中的恰好一个元素替换为范围 [-10^5, 10^5]（包含边界）内的任意整数值。
在执行这一次替换后，确定修改后数组中任意三个不同索引元素的最大可能乘积。
返回一个表示可达到的最大乘积的整数。
示例 1：
输入：nums = [-5,7,0]
输出：3500000
解释：将 0 替换为 -10^5 得到数组 [-5, 7, -10^5]，乘积为 (-5) * 7 * (-10^5) = 3500000。最大乘积为 3500000。
示例 2：
输入：nums = [-4,-2,-1,-3]
输出：1200000
解释：有两种方式可以达到最大乘积：
- [-4, -2, -3] → 将 -2 替换为 10^5 → 乘积 = (-4) * 10^5 * (-3) = 1200000
- [-4, -1, -3] → 将 -1 替换为 10^5 → 乘积 = (-4) * 10^5 * (-3) = 1200000
最大乘积为 1200000。
示例 3：
输入：nums = [0,10,0]
输出：0
解释：无法将一个元素替换为另一个整数而使数组中不包含 0。因此，所有三个元素的乘积始终为 0，最大乘积为 0。
约束条件：
3 <= nums.length <= 10^5-10^5 <= nums[i] <= 10^5
解题思路
这道题的关键insight是：为了获得最大的三元素乘积，我们应该选择数组中的两个最大值，然后将第三个位置替换为 10^5 或 -10^5。
核心思路：
贪心策略：要使三个数的乘积最大，我们需要找到数组中最大的两个数，然后考虑第三个数应该是什么。
替换选择：由于我们可以将任意一个元素替换为
[-10^5, 10^5]范围内的值，关键是确定替换为10^5还是-10^5：- 如果前两个最大数的乘积为正，第三个数应该是
10^5 - 如果前两个最大数的乘积为负，第三个数应该是
-10^5
- 如果前两个最大数的乘积为正，第三个数应该是
实现步骤：
- 对数组排序
- 取最大的两个数：
nums[n-1]和nums[n-2] - 根据它们乘积的正负性，选择合适的第三个数
- 计算最终乘积
时间复杂度：O(n log n)，主要消耗在排序上 空间复杂度：O(1)，只使用常数额外空间
这个方法简洁高效，直接利用了题目的约束条件和贪心思想。
代码实现
class Solution {
public:
long long maxProduct(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
long long first = nums[n-1];
long long second = nums[n-2];
if (first * second >= 0) {
return first * second * 100000;
} else {
return first * second * (-100000);
}
}
};
class Solution:
def maxProduct(self, nums: List[int]) -> int:
nums.sort()
n = len(nums)
first = nums[n-1]
second = nums[n-2]
if first * second >= 0:
return first * second * 100000
else:
return first * second * (-100000)
public class Solution {
public long MaxProduct(int[] nums) {
Array.Sort(nums);
int n = nums.Length;
long first = nums[n-1];
long second = nums[n-2];
if (first * second >= 0) {
return first * second * 100000;
} else {
return first * second * (-100000);
}
}
}
var maxProduct = function(nums) {
nums.sort((a, b) => a - b);
const n = nums.length;
const first = nums[n-1];
const second = nums[n-2];
if (first * second >= 0) {
return first * second * 100000;
} else {
return first * second * (-100000);
}
};
复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n log n) | 排序操作的时间复杂度 |
| 空间复杂度 | O(1) | 只使用常数额外空间 |