1464. 数组中两元素的最大乘积

题目 leetcode.cn/

• 给你一个整数数组 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

代码

function maxProduct(nums: number[]): number {
    let numsArr = nums.sort((a, b) => { return b - a });
    return (numsArr[0] - 1) * (numsArr[1] - 1)
};

• 终极简化版：
  • 要想得到两元素的最大乘积，那必须是数组中两个最大值相乘
  • 所以先将数组按照升序排序，这样最大值就在数组的最前面，返回数组前两位值减一的乘积

function maxProduct(nums: number[]): number {
    let sum = 0;
    for(let i = 0; i < nums.length - 1; i++){
        for(let k = i + 1; k < nums.length; k++){
            let count = (nums[i] - 1) * (nums[k] - 1);
            sum = Math.max(count, sum);
        }
    }
    return sum;
};

• 双重循环版：
  • 这个版本不需要排序，用双重循环把每个数字两两组合相乘，比较结果的大小，返回最大的那一个
  • 这里使用了Math.max方法来比较两个数的大小，每次遍历计算结果后都比较一次，保留当前最大的继续和下次的比较。循环结束后剩余的那个就是最大的那个

function maxProduct(nums: number[]): number {
    for(let i = 0; i < nums.length - 1; i++){
        for(let k = 0; k < nums.length - i; k++){
            if(nums[k] < nums[k+1]){
                let temp = nums[k];
                nums[k] = nums[k+1];
                nums[k+1] = temp;
            }
        }
    }
    return (nums[0] - 1) * (nums[1] - 1);
};

• 冒泡排序版：
  • 这个其实是和第一版是一样的，只不过第一版用了现成的数组API，算是偷了一个懒。然后自己又写一个一下冒泡排序，算是复习一下
  • 思路还是先排序，大的排前边，小的排后边，最后把最大的两个减去一再相乘

运行结果：

• 排序简化版

• 双重循环版

• 冒泡排序版