sliding window maximum using queue
int[] slidingWindowMaximum(int arr[], int n, int k)
{
heap = PriorityQueue()
toDrop = PriorityQueue()
// Push First K elements in the heap
for(i = 0 to k-1)
heap.push(arr[i])
ans = []
// store the maximum in ans
ans.append(heap.top())
//iterate for rest elements
for(i = k to n)
{
// pop the heap if leftmost element is previous element was maximum
if(arr[i-k] == heap.top())
heap.pop()
else
{
// push the leftmost element to toDrop heap
toDrop.push(arr[i-k])
}
// pop elements from both heap till their top matches
while(!toDrop.isEmpty() and toDrop.top() == heap.top())
{
heap.pop()
toDrop.pop()
}
// push the element to the heap
heap.push(arr[i])
ans.append(heap.top())
}
return ans
}