# C++, 69ms solution using heaps

• 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;
}
};``````

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