[LeetCode C++实现]1464. Maximum Product of Two Elements in an Array
date: 2020-10-06 16:00
url: LeetCode1464
1464. Maximum Product of Two Elements in an Array
无脑常规暴力破解方法:

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        int maximum = INT_MIN;
        for(int i = 0;i < n;i++)
        {
            for(int j = i + 1;j < n;j++)
            {
                maximum = max(maximum,(nums[i] - 1) * (nums[j] - 1));
            }
        }
        
        return maximum;
    }
};

运行速度也是符合预期,仅击败8.69%C++提交。

Runtime: 48 ms, faster than 8.69% of C++ online submissions for Maximum Product of Two Elements in an Array.
Memory Usage: 10.3 MB, less than 8.07% of C++ online submissions for Maximum Product of Two Elements in an Array.

这里我们注意到nums中的值都是正数,可以将程序优化为只遍历一遍,找到最大值和次大值即可。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int m = INT_MIN,n = INT_MIN;
        for(auto num : nums)
        {
            if(num > m)
                n = exchange(m,num);
            else
                n = max(n,num);
        }
        
        return (m - 1) *(n - 1);
    }
};

这里的exchange和swap的区别是exchange返回的是旧值。