"sliding window maximum" Code Answer's

maximum element in a window of size k

By DarkPhilosopher on Apr 28, 2020

#include <bits/stdc++.h> 

using namespace std; 

// A Dequeue (Double ended queue) based method for printing maximum element of 
// all subarrays of size k 
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<int> 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()]; 
} 

// Driver program to test above functions 
int main() 
{ 
	int arr[] = { 12, 1, 78, 90, 57, 89, 56 }; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	int k = 3; 
	printKMax(arr, n, k); 
	return 0; 
} 

Add Comment

sliding window maximum

By Faithful Fowl on May 22, 2021

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
}

Source: afteracademy.com

Add Comment