LeetCode 1464. 数组中两元素的最大乘积
题目描述
题意分析
从不同下标取出两个元素，最大化
(nums[i]-1)×(nums[j]-1)。下标必须不同，但两个元素的值可以相同。题目保证所有元素至少为
1，减一后的因子都非负。增大其中任意一个因子都不会让乘积变小，所以应取数组中最大的两个元素，无需枚举所有下标对。
解法：一次扫描维护最大两值
核心思路
[!blue]
扫描过程中，用
first和second保存已处理元素中最大的两个值，并始终满足first >= second。这里按元素出现的次数排名，不对相同数值去重。新值
num若大于first，它成为新的第一大，而旧first一定成为第二大；因此先执行second = first，再更新first。否则，第一大不变，只需判断num是否大于second，决定它能否替换第二大。若
num等于first但大于second，它会进入第二个分支，两个不同位置的相等最大值就都被保留。若两个候选已经相等，再遇到同值无需更新，现有两个位置已经足够。数组至少有两个元素，先用前两项按大小初始化，从下标
2开始扫描。每轮只处理一个新位置并进入一个更新分支，因而两个候选始终来自不同元素；扫描结束时，将这两个值各减一后相乘即可。
解题步骤
- 用前两个元素的较大值初始化
first，较小值初始化second。- 从第三个元素开始扫描。若当前值超过
first，将旧第一大移到第二大，再保存新第一大。- 否则只在当前值超过
second时更新第二大，其余情况保持两个候选不变。- 返回
(first-1)×(second-1)。
代码实现
class Solution {
public int maxProduct(int[] nums) {
int first = Math.max(nums[0], nums[1]);
int second = Math.min(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
int num = nums[i];
if (num > first) {
// 新值成为第一大前，先把旧第一大降为第二大。
second = first;
first = num;
} else if (num > second) {
// 另一个相同最大值也能占据第二名，允许数值相等。
second = num;
}
}
return (first - 1) * (second - 1);
}
}
func maxProduct(nums []int) int {
first, second := nums[0], nums[1]
if first < second {
first, second = second, first
}
for i := 2; i < len(nums); i++ {
num := nums[i]
if num > first {
// 新值成为第一大前，先把旧第一大降为第二大。
second = first
first = num
} else if num > second {
// 另一个相同最大值也能占据第二名，允许数值相等。
second = num
}
}
return (first - 1) * (second - 1)
}
复杂度分析
- 时间复杂度：$O(n)$。每个元素只参与常数次比较与赋值。
- 空间复杂度：$O(1)$。只维护两个最大值，不修改输入数组。
关键点总结
[!green]
- 取两个最大值的依据是减一后的因子非负，这使乘积对每个因子都单调不减。
- 第二大按不同元素计数，允许与第一大数值相同。
- 新第一大出现时，旧第一大仍应保留，不能直接丢弃。
易错点总结
[!yellow]
- 两个更新分支写成独立的
if，可能把同一个新元素同时放进两个候选位置。- 先覆盖
first再执行second = first，会丢失旧第一大并重复使用当前元素。- 忽略等于第一大的新值，会错过两个不同下标上的相等最大值。
- 用前两个位置初始化后，又从下标
0开始扫描，会把已经计入的元素再次当作新候选。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 628. 三个数的最大乘积 | 简单 | 同样只需维护少数极值，本题输入为正且选择两项，原题三项乘积还要考虑两个负数。 |
| 414. 第三大的数 | 简单 | 原题按不同值找第三大，本题两个相等最大值都可参与，不能先去重。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！