3. Sliding Window maximum code example
Example: sliding window maximum
int[] slidingWindowMaximum(int arr[], int n, int k)
{
q = Dequeue()
ans = []
// for First K elements
for( i = 0 to k-1)
{
while(!q.empty() and arr[i] >= arr[q.back()])
{
// Remove the indices of elements that are smaller than the current elements
q.pop_back()
}
q.push_back(i)
}
// the element at the front has index of the highest element in the window
ans.append(arr[q.front()])
// for rest elements
for(i = k to n-1)
{
// drop the elements that are out of window
while(!q.empty() and q.front() <= i-k)
q.pop_front()
// remove those elements smaller than the current element from back
while(!q.empty() and arr[i] >= arr[q.back()])
q.pop_back()
q.push_back(i)
ans.append(arr[q.front()])
}
return ans
}