1464. 数组中两元素的最大乘积
1464. 数组中两元素的最大乘积
🟢 🔖 数组
排序
堆(优先队列)
🔗 力扣
LeetCode
题目
Given the array of integers nums
, you will choose two different indices i
and j
of that array. Return the maximum value of(nums[i]-1)*(nums[j]-1)
.
Example 1:
Input: nums = [3,4,5,2]
Output: 12
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is,
(nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12
.
Example 2:
Input: nums = [1,5,4,5]
Output: 16
Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of
(5-1)*(5-1) = 16
.
Example 3:
Input: nums = [3,7]
Output: 12
Constraints:
2 <= nums.length <= 500
1 <= nums[i] <= 10^3
题目大意
给你一个整数数组 nums
,请你选择数组的两个不同下标 i
和 j
,使 (nums[i]-1)*(nums[j]-1)
取得最大值。
请你计算并返回该式的最大值。
示例 1:
输入: nums = [3,4,5,2]
输出: 12
解释: 如果选择下标 i=1 和 j=2(下标从 0 开始),则可以获得最大值,
(nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12
。
示例 2:
输入: nums = [1,5,4,5]
输出: 16
解释: 选择下标 i=1 和 j=3(下标从 0 开始),则可以获得最大值
(5-1)*(5-1) = 16
。
示例 3:
输入: nums = [3,7]
输出: 12
提示:
2 <= nums.length <= 500
1 <= nums[i] <= 10^3
解题思路
问题要求从数组中选择两个不同的下标,使得 (nums[i] - 1) * (nums[j] - 1)
的值最大。最优的选择显然是数组中的两个最大值。
遍历数组,维护两个变量:
max
:当前最大的数字。second
:当前第二大的数字。
遍历时:
- 如果当前数字比
max
大:- 更新
second
为之前的max
。 - 更新
max
为当前数字。
- 更新
- 否则,如果当前数字比
second
大,更新second
。
- 如果当前数字比
计算结果为
(max - 1) * (second - 1)
。
复杂度分析
- 时间复杂度:
O(n)
,只需一次遍历数组。 - 空间复杂度:
O(1)
,仅使用常数级别的额外空间。
代码
/**
* @param {number[]} nums
* @return {number}
*/
var maxProduct = function (nums) {
let max = 0,
second = 0;
for (let num of nums) {
if (num > max) {
second = max;
max = num;
} else if (num > second) {
second = num;
}
}
return (max - 1) * (second - 1);
};