The approach is not clear
The approach is not clear
here is a stack based approach
Approach: If you know for every index i an index j ≥ i such that max(a[i], a[i + 1], … a[j]) = a[i]. Lets call it max_upto[i]. Then if you want to know the maximum element in the sub-array of length k starting from ith index you can get it by checking every index starting from i to i + k – 1 for which max_upto[i] ≥ i + k – 1 (last index of that window).
=
void print_max(int a[], int n, int k)
{
// max_upto array stores the index
// upto which the maximum element is a[i]
// i.e. max(a[i], a[i + 1], … a[max_upto[i]]) = a[i]
int max_upto[n];
// Update max_upto array similar to
// finding next greater element
stack<int> s;
s.push(0);
for (int i = 1; i < n; i++) {
while (!s.empty() && a[s.top()] < a[i]) {
max_upto[s.top()] = i - 1;
s.pop();
}
s.push(i);
}
while (!s.empty()) {
max_upto[s.top()] = n - 1;
s.pop();
}
int j = 0;
for (int i = 0; i <= n - k; i++) {
// j < i is to check whether the
// jth element is outside the window
while (j < i || max_upto[j] < i + k - 1)
j++;
cout << a[j] << " ";
}
cout << endl;
}
the deque based approach is similar
just consider that u have to push the index of the greatest element in the first window
and store the max in deque
now in the deque
if the current max is out of window u simply pop it out
then slide it one forward and check if the new element enter is greater than the max of the previous one
if yes then this is the new max for this window and we will pop while this is true (compare front and a[i])
then insert the current element
void printKMax(int arr[], int n, int k)
{
// Create a Double Ended Queue, Qi that will store indexes of array elements
// The queue will store indexes of useful elements in every window and it will
// maintain decreasing order of values from front to rear in Qi, i.e.,
// arr[Qi.front[]] to arr[Qi.rear()] are sorted in decreasing order
std::deque Qi(k);
/* Process first k (or first window) elements of array */
int i;
for (i = 0; i < k; ++i) {
// For every element, the previous smaller elements are useless so
// remove them from Qi
while ((!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back(); // Remove from rear
// Add new element at rear of queue
Qi.push_back(i);
}
// Process rest of the elements, i.e., from arr[k] to arr[n-1]
for (; i < n; ++i) {
// The element at the front of the queue is the largest element of
// previous window, so print it
cout << arr[Qi.front()] << " ";
// Remove the elements which are out of this window
while ((!Qi.empty()) && Qi.front() <= i - k)
Qi.pop_front(); // Remove from front of queue
// Remove all elements smaller than the currently
// being added element (remove useless elements)
while ((!Qi.empty()) && arr[i] >= arr[Qi.back()])
Qi.pop_back();
// Add current element at the rear of Qi
Qi.push_back(i);
}
// Print the maximum element of last window
cout << arr[Qi.front()];
}
I would advise you to solve the next greatest element problem for better clarity