C++, 69ms solution using heaps


  • 0
    V

    The idea is to maintain a maxHeap of size k (which can grow further than size k, as explained below).
    A number is to be evicted from this heap if the k-sized window moves past it.

    • If that number to be evicted is at the top, immediately pop the heap.
    • if not, then maintain a toDelete heap which will evict the number as soon as it reaches top in both. Keep discarding numbers from both these heaps until the tops don't match.
    • Continue until you run through the entire heap.

    Complexity: worst ~ n * log(n), average ~ n * log(k)

    public:
        vector<int> maxSlidingWindow(vector<int>& nums, int k) {
            priority_queue<int> heap;
            priority_queue<int> toDelete;
    
            vector<int> result;
            
            if(nums.empty())
                return result;
            
            for(int i = 0; i < k; ++i)
                heap.push(nums[i]);
            
            result.push_back(heap.top());
            
            for(int i = k; i < nums.size(); ++i) {
                if(nums[i - k] == heap.top())
                    heap.pop();
                else
                    toDelete.push(nums[i - k]);
                
                while(!toDelete.empty() && toDelete.top() == heap.top()) {
                    heap.pop();
                    toDelete.pop();
                }
                
                heap.push(nums[i]);
                result.push_back(heap.top());
            }
            
            return result;
        }
    };

Log in to reply
 

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