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)