Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of(nums[i]-1)*(nums[j]-1).
Example 1:
Input: nums = [3,4,5,2] Output: 12 Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12.
Example 2:
Input: nums = [1,5,4,5] Output: 16 Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16.
Example 3:
Input: nums = [3,7] Output: 12
Constraints:
2 <= nums.length <= 5001 <= nums[i] <= 10^3
Solution 1: Sort
We want to find the largest and second largest elements.
Time complexity: O(nlogn)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 |
// Author: Huahua class Solution { public: int maxProduct(vector<int>& nums) { sort(rbegin(nums), rend(nums)); return (nums[0] - 1) * (nums[1] - 1); } }; |
Solution 2: Without sorting
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: int maxProduct(vector<int>& nums) { int m1 = 0; int m2 = 0; for (int n : nums) { if (n > m1) { m2 = m1; m1 = n; } else if (n > m2) { m2 = n; } } return (m1 - 1) * (m2 - 1); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment