C++ O(n) priority queue


  • 0
    B

    if all number are positive, the solution would be the largest three number

    if there are negative number, we also need to consider the smallest two number could form a large positive number

    using priority queue could find the target number in one pass, it is almost O(n)

    class Solution {
    public:
        int maximumProduct(vector<int>& nums) {
            priority_queue<int>pq1;
            priority_queue<int,vector<int>,greater<int>>pq2;
            
            for(auto e : nums)
            {
                pq1.push(e);
                pq2.push(e);
                while(pq1.size() > 2) pq1.pop();
                while(pq2.size() > 3) pq2.pop();
            }
            int ans1 = pq1.top();
            pq1.pop();
            ans1 *= pq1.top();
            
            int ans = pq2.top();
            pq2.pop();
            ans *= pq2.top();
            pq2.pop();
            
            ans = max(ans1, ans);
            return ans*pq2.top();
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.