Imprima el mínimo de todos los subarreglos usando el conjunto en C++ STL

Dada una array de tamaño N y un número entero K, encuentre el mínimo para todos y cada uno de los subarreglos contiguos de tamaño K.

Ejemplos :

Input : arr[] = {5, 3, 4, 1, 1}, K = 3
Output : 3 1 1

Input : arr[] = {1, 2, 3, 4, 1, 6, 7, 8, 2, 1}, K = 4
Output : 1 1 1 1 1 2 1

requisito previo :

• Técnica de ventana corrediza
• Establecer en C++ STL

Set realiza la operación de inserción y extracción en tiempo o(logK) y siempre almacena las claves en el orden ordenado.

La idea es utilizar un conjunto de pares donde el primer elemento del par es el elemento mismo y el segundo elemento del par contiene el índice de array del elemento.

En el programa se utiliza el siguiente enfoque:

1. Elija los primeros k elementos y cree un conjunto de pares con estos elementos y su índice como se describe anteriormente.
2. Ahora, use la técnica de deslizamiento de ventana y bucle de j = 0 a nk:
   • Obtenga el elemento mínimo del conjunto en la ventana actual e imprímalo. (El primer elemento)
   • Busque el elemento más a la izquierda de la ventana actual en el conjunto y elimínelo.
   • Inserte el siguiente elemento de la ventana actual en el conjunto para pasar a la siguiente ventana.

¿Por qué usamos un conjunto de pares en lugar de un conjunto?

Un conjunto no permite la inserción de elementos duplicados y una ventana de tamaño k puede tener cualquier número de elementos duplicados. Entonces, insertamos un par del elemento y su índice en el conjunto.

A continuación se muestra la implementación del enfoque anterior:

// CPP program to print Minimum of
// all Subarrays using set in C++ STL
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to print Minimum of
// all Subarrays using set in C++ STL
void minOfSubarrays(int arr[], int n, int k)
{
    // Create a set of pairs
    set<pair<int, int> > q;
  
    // Create an iterator to the set
    set<pair<int, int> >::iterator it;
  
    // Insert the first k elements along
    // with their indices into the set
    for (int i = 0; i < k; i++) {
        q.insert(pair<int, int>(arr[i], i));
    }
  
    for (int j = 0; j < n - k + 1; j++) {
  
        // Iterator to the beginning of the
        // set since it has the minimum value
        it = q.begin();
  
        // Print the minimum element
        // of current window
        cout << it->first << " ";
  
        // Delete arr[j](Leftmost element of
        // current window) from the set
        q.erase(pair<int, int>(arr[j], j));
  
        // Insert next element
        q.insert(pair<int, int>(arr[j + k], j + k));
    }
}
  
// Driver Code
int main()
{
    int arr[] = { 5, 3, 4, 1, 1 };
  
    int K = 3;
  
    int n = sizeof(arr) / sizeof(arr[0]);
  
    minOfSubarrays(arr, n, K);
  
    return 0;
}

3 1 1

Complejidad de tiempo : O (N * LogK)