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