Easy

题目描述

给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。

返回一个能够获得最大值的 (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) 的值最大。

思路分析：

由于要使 (nums[i]-1)*(nums[j]-1) 最大，我们需要找到数组中最大的两个元素。因为所有元素都是正数，所以最大的两个数相乘得到的结果必然是最大的。

解法一：暴力遍历（O(n²)） 使用两层循环遍历所有可能的 i 和 j 组合，计算每种组合的乘积值，记录最大值。

解法二：排序法（O(n log n)） 对数组进行排序，取最大的两个元素进行计算。

解法三：一次遍历找最大两数（O(n)） 【推荐】 只需要遍历一次数组，记录最大值和次大值。由于我们只需要两个最大的数，这种方法时间复杂度最优。

具体实现：维护两个变量 first 和 second，分别表示当前遇到的最大值和次大值。遍历数组时，如果当前元素大于 first，则更新 second = first，first = current；如果当前元素大于 second 但小于等于 first，则更新 second = current。

最后返回 (first-1) * (second-1) 即可。

代码实现

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int first = 0, second = 0;
        
        for (int num : nums) {
            if (num > first) {
                second = first;
                first = num;
            } else if (num > second) {
                second = num;
            }
        }
        
        return (first - 1) * (second - 1);
    }
};

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        first = second = 0
        
        for num in nums:
            if num > first:
                second = first
                first = num
            elif num > second:
                second = num
        
        return (first - 1) * (second - 1)

public class Solution {
    public int MaxProduct(int[] nums) {
        int first = 0, second = 0;
        
        foreach (int num in nums) {
            if (num > first) {
                second = first;
                first = num;
            } else if (num > second) {
                second = num;
            }
        }
        
        return (first - 1) * (second - 1);
    }
}

var maxProduct = function(nums) {
    let first = 0, second = 0;
    
    for (let num of nums) {
        if (num > first) {
            second = first;
            first = num;
        } else if (num > second) {
            second = num;
        }
    }
    
    return (first - 1) * (second - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(1)

其中 n 是数组的长度。我们只需要遍历数组一次，使用常数个额外变量。