Saltar al contenido

ejemplo de código c ++ máximo de ventana deslizante

Si encuentras alguna parte que te causa duda puedes dejarlo en la sección de comentarios y trataremos de ayudarte rápidamente.

Ejemplo 1: elemento máximo en una ventana de tamaño k

#include  

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; 

Ejemplo 2: ventana deslizante mínima c ++

void sliding_window_minimum(std::vector<int> & ARR, int K) 
  // pair<int,int> represents the pair (ARR[i], i)
  std::deque< std::pair<int,int> > window;
  for (int i = 0; i < ARR.size(); i++) 
     while (!window.empty() && window.back().first >= ARR[i])
       window.pop_back();
     window.push_back(std::make_pair(ARR[i], i));

     while(window.front().second <= i - K)
       window.pop_front();

     std::cout << (window.front().first) << ' ';
  

Reseñas y valoraciones

Recuerda compartir este enunciado si si solucionó tu problema.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *