algorithm - Finding maximum for every window of size k in an array -

Given an array of shapes n and k, how do you get the maximum for each corresponding subarray of size?

For example

  arr = 1 5 2 6 3 1 24 7 k = 3 ans = 5 6 6 6 24 24   < P> I was thinking of having an array of size k and extracting the last element in each step and adding the new element to get the maximum number. It leads to the running time of O (nk) is there a better way to do this?   
 
 
 You need a fast data structure that can be added, removed and less than O (N) Query for the maximum element in time (you can use only one array if you are allowed by O (N) or O (NLON)) You can use a Hep, a balanced binary search tree, a drop list or any other sorted data structure that executes these actions in O (Log (N)).  
 The good news is that the most popular language is the sort of data structure you have to support these operations in C ++ in  std :: set  and  std: : Multiset  (you probably need it later) and in Java there is  TreeSet .