【2022-08-26每日一题】1464. 数组中两元素的最大乘积
2022-08-26
1分钟阅读时长
2022-08-26每日一题：1464. 数组中两元素的最大乘积
- 难度：Easy
- 标签：数组 、 排序 、 堆（优先队列）
给你一个整数数组 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 <= 5001 <= nums[i] <= 10^3
方法一：一次遍历找出最大的两个数
func maxProduct(nums []int) int {
a, b := nums[0], nums[1]
for i := 2; i < len(nums); i++ {
// 每次和最小的数进行比较并更新对应数字
if a < b && a < nums[i] {
a = nums[i]
} else if b < nums[i] {
b = nums[i]
}
}
return (a-1)*(b-1)
}
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
方法二：排序，取最大两个数
func maxProduct(nums []int) int {
sort.Ints(nums)
return (nums[len(nums)-1]-1)*(nums[len(nums)-2]-1)
}
复杂度分析
- 时间复杂度：O(nlogn)
- 空间复杂度：O(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++ {
if first < nums[i] {
first, second = nums[i], first
} else if b < nums[i] {
second = nums[i]
}
}
return (first-1)*(second-1)
}
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)