写在前面
难度：简单排序、取第1/2个元素减1乘积
sort<nums.begin(), nums.end(), greater<int>()>
题目详情
给你一个整数数组 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
ac代码
方法1：排序 + 求积
class Solution
{
public:
int maxProduct(vector<int>& nums)
{
sort(nums.begin(), nums.end(), greater<int>());
return (nums[0]-1)*(nums[1]-1);
}
};
方法2：单层循环 + 多个临时变量（第1/2最大值）
class Solution
{
public:
int maxProduct(vector<int>& nums)
{
int max1 = 0, max2 = 0;
for(int i=0; i<nums.size(); i++)
{
if(nums[i]>=max1)
{
max2 = max1;
max1 = nums[i];
}
else if(nums[i]<=max1 && nums[i]>max2)
max2 = nums[i];
}
return (max1-1)*(max2-1);
}
};
测试代码
#include<vector>
#include<iostream>
using namespace std;
int maxProduct(vector<int>& nums)
{
int max1 = 0, max2 = 0;
for(int i=0; i<nums.size(); i++)
{
if(nums[i]>=max1)
{
max2 = max1;
max1 = nums[i];
}
else if(nums[i]<=max1 && nums[i]>max2)
max2 = nums[i];
}
return (max1-1)*(max2-1);
}
int main()
{
vector<int> vv = {3, 7};
cout << maxProduct(vv) << endl;
}
参考文章
leetcode（1464） 数组中两元素的最大乘积
Processed:
0.010, SQL:
9
