A simple O ( n*log(k) ) solution using multiset


  • 2
    K
    class Solution {
    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    
            multiset<int, greater<int>> window; // almost like a max-heap
            vector<int> out;
    
            int n = nums.size();
            
            for (int i = 0; i < n; ++i) {
    
                window.insert( nums[i] );
                
                if (i >= (k-1)) {
                    
                    // first element is the ordered multiset is max
                    out.push_back(*window.begin());
    
                    // remove first key in the 'window' //
                    auto it = window.find( nums[i-k+1] ); // O( log(k) ) operation
                    window.erase( it ); // O( log(k) ) operation
                }
            }
            
            return out;
        }
    };

Log in to reply
 

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