【力扣1464】数组中两元素的最大乘积

• 👑专栏内容：力扣刷题
• ⛪个人主页：子夜的星的主页
• 💕座右铭：前路未远，步履不停

---

---

一、题目描述

题目链接：数组中两元素的最大乘积

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

二、题目分析

在整型数组里面求 (nums[i]-1)*(nums[j]-1) 的最大值，仔细分析一下，本质上就是在求整型数组种最大的两个数。那么如何找到两个数的最大值呢？

第一种思路是将数组排序，然后直接找到排序后的最后两个数。通过对数组进行升序排序，最大的两个数将位于数组的末尾，这样可以直接取得这两个数。

第二种思路是维护最大值和次大值。我们可以遍历数组，同时更新最大值和次大值。如果当前元素大于最大值，则将最大值更新为当前元素；如果当前元素介于最大值和次大值之间，则将次大值更新为当前元素。遍历完数组后，最大值和次大值即为数组中的两个最大数

1、排序

在Java种可以使用Arrays.sort来进行排序，该方法默认按照升序（从小到大）对数组进行排序。

class Solution {
    public int maxProduct(int[] nums) {
        Arrays.sort(nums); 
        return (nums[nums.length - 1] -1 ) * (nums[nums.length - 2] -1 );
    }
}
1
2
3
4
5
6

2、最值模拟

最值模拟是指在一个线性结构中，通过遍历元素逐个比较，模拟求取最大值或最小值的过程。
这道题的本质是求最大值和次大值，那么我们就可以用最值模拟，遍历元素逐个比较，模拟求得最大值和次大值。

class Solution {
    public int maxProduct(int[] nums) {
        int max = 0;
        int secondMax = 0;
        for(int i = 0;i<nums.length;i++){
            if(nums[i]>max){
                secondMax = max; 
                max = nums[i];
            }else if(nums[i] > secondMax){
                secondMax = nums[i];
            }
        }
        return (max -1 ) * (secondMax - 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15