The question can be tackled by multiple approaches. I am gonna shed light on all the approaches one by one .

The **First Approach** is by using a balanced binary search tree and calculating maximum by inserting and deleting elements from the range. In c++ there is a cool implementation of BST called set . You can perform insert/delete operations in set in **logn** and that is what we want. So coming to the final solution what we will do is , first we will push all the elements in range [0, w-1] in set and find the maximum in set using ***s.rbegin()** , now for each range ahead our initial range we will delete the *start* and insert the *end+1* and find maximum for updated set . The total complexity of this algorithm will come out to **nlogk** .

here is the code in c++ - -

```
vector<int> Solution::slidingMaximum(const vector<int> &A, int B) {
multiset<int> s;
multiset<int>::iterator it;
int st = 0;
int en = st+B-1;
for(int i = st; i <= en; i++){
s.insert(A[i]);
}
int max1 = *s.rbegin();
vector<int> v;
v.push_back(max1);
while(en+1 < A.size()){
it = s.find(A[st]);
s.erase(it);
st = st+1;
en = en+1;
s.insert(A[en]);
max1 = *s.rbegin();
v.push_back(max1);
}
return v;
}
```

Another approach is O(n) by using a Dequeue . We create a Dequeue, Qi of capacity k, that stores only useful elements of current window of k elements. An element is useful if it is in current window and is greater than all other elements on left side of it in current window. We process all array elements one by one and maintain Qi to contain useful elements of current window and these useful elements are maintained in sorted order. The element at front of the Qi is the largest and element at rear of Qi is the smallest of current window.

here is the code in c++ -

```
class Solution {
public:
vector<int> slidingMaximum(vector<int> &A, int w) {
int n = A.size();
vector<int> B;
if (n < w) return B;
B.resize(n - w + 1);
deque<int> Q;
for (int i = 0; i < w; i++) {
while (!Q.empty() && A[i] >= A[Q.back()])
Q.pop_back();
Q.push_back(i);
}
for (int i = w; i < n; i++) {
B[i - w] = A[Q.front()];
while (!Q.empty() && A[i] >= A[Q.back()])
Q.pop_back();
while (!Q.empty() && Q.front() <= i - w)
Q.pop_front();
Q.push_back(i);
}
B[n - w] = A[Q.front()];
return B;
}
};
```