LeetCode刷题（153）～数组中两元素的最大乘积【 priority_queue 】

题目描述

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

  
 

  
1
  
2
  
3
 

示例 2：

输入：nums = [1,5,4,5]
输出：16
解释：选择下标 i=1 和 j=3（下标从 0 开始），则可以获得最大值 (5-1)*(5-1) = 16 。

  
 

  
1
  
2
  
3
 

示例 3：

输入：nums = [3,7]
输出：12

  
 

  
1
  
2
 

提示：

• 2 <= nums.length <= 500
• 1 <= nums[i] <= 10^3

解答 By 海轰

提交代码【 sort()排序 】

int maxProduct(vector<int>& nums) { sort(nums.begin(),nums.end()); int n=nums.size()-1; return (nums[n]-1)*(nums[n-1]-1); }

  
 

  
1
  
2
  
3
  
4
  
5
 

运行结果

提交代码【循环遍历寻找第一、第二大的值】

int maxProduct(vector<int>& nums) { int num1=0;// 最大值 int num2=0;// 第二大值 for(int num:nums) { if(num>num1) { num2=num1; num1=num; } else { num2= num>num2? num:num2; } } return (num1-1)*(num2-1); }

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

运行结果

提交代码【堆排序】

int maxProduct(vector<int>& nums) { priority_queue<int,vector<int>,greater<int>> pq; for(int num:nums) { if(pq.size()==2) { if(pq.top()<num) { pq.pop(); pq.push(num); } } else { pq.push(num); } } int num1=pq.top(); pq.pop(); int num2=pq.top(); return (num1-1)*(num2-1); }

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-of-two-elements-in-an-array

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108566802