Conjunto 1: Máximo de ventana deslizante (Máximo de todos los subarreglos de tamaño k) .
Dada una array arr de tamaño N y un entero K , la tarea es encontrar el máximo para todos y cada uno de los subarreglos contiguos de tamaño K.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, K = 3
Salida: 3 3 4 5 5 5 6
Todos los subarreglos contiguos de tamaño k son
{1, 2, 3} => 3
{2, 3, 1} => 3
{3, 1, 4} => 4
{1, 4, 5} => 5
{4, 5, 2} => 5
{5, 2, 3} => 5
{2, 3, 6} => 6Entrada: arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, K = 4
Salida: 10 10 10 15 15 90 90
Enfoque: Para resolver esto en menor complejidad espacial podemos usar la técnica de dos punteros .
- El primer puntero de variable itera a través del subarreglo y encuentra el elemento máximo de un tamaño K dado
- El segundo puntero de variable marca el índice final del primer puntero de variable, es decir, (i + K – 1) índice .
- Cuando el puntero de la primera variable alcanza el índice del puntero de la segunda variable, el máximo de ese subarreglo se ha calculado y se imprimirá.
- El proceso se repite hasta que el puntero de la segunda variable alcanza el último índice de array (es decir, array_size – 1) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the maximum for each
// and every contiguous subarray of size K
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum for each
// and every contiguous subarray of size k
void printKMax(int a[], int n, int k)
{
// If k = 1, print all elements
if (k == 1) {
for (int i = 0; i < n; i += 1)
cout << a[i] << " ";
return;
}
// Using p and q as variable pointers
// where p iterates through the subarray
// and q marks end of the subarray.
int p = 0,
q = k - 1,
t = p,
max = a[k - 1];
// Iterating through subarray.
while (q <= n - 1) {
// Finding max
// from the subarray.
if (a[p] > max)
max = a[p];
p += 1;
// Printing max of subarray
// and shifting pointers
// to next index.
if (q == p && p != n) {
cout << max << " ";
q++;
p = ++t;
if (q < n)
max = a[q];
}
}
}
// Driver Code
int main()
{
int a[] = { 1, 2, 3, 4, 5,
6, 7, 8, 9, 10 };
int n = sizeof(a) / sizeof(a[0]);
int K = 3;
printKMax(a, n, K);
return 0;
}
Java
// Java program to find the maximum for each
// and every contiguous subarray of size K
import java.util.*;
class GFG{
// Function to find the maximum for each
// and every contiguous subarray of size k
static void printKMax(int a[], int n, int k)
{
// If k = 1, print all elements
if (k == 1) {
for (int i = 0; i < n; i += 1)
System.out.print(a[i]+ " ");
return;
}
// Using p and q as variable pointers
// where p iterates through the subarray
// and q marks end of the subarray.
int p = 0,
q = k - 1,
t = p,
max = a[k - 1];
// Iterating through subarray.
while (q <= n - 1) {
// Finding max
// from the subarray.
if (a[p] > max)
max = a[p];
p += 1;
// Printing max of subarray
// and shifting pointers
// to next index.
if (q == p && p != n) {
System.out.print(max+ " ");
q++;
p = ++t;
if (q < n)
max = a[q];
}
}
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 1, 2, 3, 4, 5,
6, 7, 8, 9, 10 };
int n = a.length;
int K = 3;
printKMax(a, n, K);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find the maximum for each # and every contiguous subarray of size K # Function to find the maximum for each # and every contiguous subarray of size k def printKMax(a, n, k): # If k = 1, print all elements if (k == 1): for i in range(n): print(a[i], end=" "); return; # Using p and q as variable pointers # where p iterates through the subarray # and q marks end of the subarray. p = 0; q = k - 1; t = p; max = a[k - 1]; # Iterating through subarray. while (q <= n - 1): # Finding max # from the subarray. if (a[p] > max): max = a[p]; p += 1; # Printing max of subarray # and shifting pointers # to next index. if (q == p and p != n): print(max, end=" "); q += 1; p = t + 1; t = p; if (q < n): max = a[q]; # Driver Code if __name__ == '__main__': a = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; n = len(a); K = 3; printKMax(a, n, K); # This code is contributed by Princi Singh
C#
// C# program to find the maximum for each
// and every contiguous subarray of size K
using System;
class GFG{
// Function to find the maximum for each
// and every contiguous subarray of size k
static void printKMax(int []a, int n, int k)
{
// If k = 1, print all elements
if (k == 1) {
for (int i = 0; i < n; i += 1)
Console.Write(a[i]+ " ");
return;
}
// Using p and q as variable pointers
// where p iterates through the subarray
// and q marks end of the subarray.
int p = 0,
q = k - 1,
t = p,
max = a[k - 1];
// Iterating through subarray.
while (q <= n - 1) {
// Finding max
// from the subarray.
if (a[p] > max)
max = a[p];
p += 1;
// Printing max of subarray
// and shifting pointers
// to next index.
if (q == p && p != n) {
Console.Write(max+ " ");
q++;
p = ++t;
if (q < n)
max = a[q];
}
}
}
// Driver Code
public static void Main(String[] args)
{
int []a = { 1, 2, 3, 4, 5,
6, 7, 8, 9, 10 };
int n = a.Length;
int K = 3;
printKMax(a, n, K);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find the maximum for each
// and every contiguous subarray of size K
// Function to find the maximum for each
// and every contiguous subarray of size k
function printKMax(a, n, k)
{
// If k = 1, print all elements
if (k == 1) {
for (let i = 0; i < n; i += 1)
document.write(a[i] + " ");
return;
}
// Using p and q as variable pointers
// where p iterates through the subarray
// and q marks end of the subarray.
let p = 0, q = k - 1, t = p, max = a[k - 1];
// Iterating through subarray.
while (q <= n - 1) {
// Finding max
// from the subarray.
if (a[p] > max)
max = a[p];
p += 1;
// Printing max of subarray
// and shifting pointers
// to next index.
if (q == p && p != n) {
document.write(max + " ");
q++;
p = ++t;
if (q < n)
max = a[q];
}
}
}
// Driver Code
let a = [ 1, 2, 3, 4, 5,
6, 7, 8, 9, 10 ];
let n = a.length
let K = 3;
printKMax(a, n, K);
</script>
Producción
3 4 5 6 7 8 9 10
Complejidad de tiempo: O(N*k)
Complejidad de espacio auxiliar: O(1)
Enfoque 2: Usando Programación Dinámica:
- En primer lugar, divida toda la array en bloques de k elementos de modo que cada bloque contenga k elementos de la array (no siempre para el último bloque).
- Mantenga dos arrays de dp, a saber, izquierda y derecha.
- left[i] es el máximo de todos los elementos que están a la izquierda del elemento actual (incluido el elemento actual) en el bloque actual (bloque en el que está presente el elemento actual).
- De manera similar, right[i] es el máximo de todos los elementos que están a la derecha del elemento actual (incluido el elemento actual) en el bloque actual (bloque en el que está presente el elemento actual).
- Finalmente, al calcular el elemento máximo en cualquier subarreglo de longitud k, calculamos el máximo de right[l] e left[r]
donde l = índice inicial del subarreglo actual, r = índice final del subarreglo actual
A continuación se muestra la implementación del enfoque anterior,
C++
// C++ program to find the maximum for each
// and every contiguous subarray of size K
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum for each
// and every contiguous subarray of size k
void printKMax(int a[], int n, int k)
{
// If k = 1, print all elements
if (k == 1) {
for (int i = 0; i < n; i += 1)
cout << a[i] << " ";
return;
}
//left[i] stores the maximum value to left of i in the current block
//right[i] stores the maximum value to the right of i in the current block
int left[n],right[n];
for(int i=0;i<n;i++){
//if the element is starting element of that block
if(i%k == 0) left[i] = a[i];
else left[i] = max(left[i-1],a[i]);
//if the element is ending element of that block
if((n-i)%k == 0 || i==0) right[n-1-i] = a[n-1-i];
else right[n-1-i] = max(right[n-i],a[n-1-i]);
}
for(int i=0,j=k-1; j<n; i++,j++)
cout << max(left[j],right[i]) << ' ';
}
// Driver Code
int main()
{
int a[] = { 1, 2, 3, 4, 5,
6, 7, 8, 9, 10 };
int n = sizeof(a) / sizeof(a[0]);
int K = 3;
printKMax(a, n, K);
return 0;
}
Java
// Java program to find the maximum for each
// and every contiguous subarray of size K
import java.util.*;
class GFG
{
// Function to find the maximum for each
// and every contiguous subarray of size k
static void printKMax(int a[], int n, int k)
{
// If k = 1, print all elements
if (k == 1) {
for (int i = 0; i < n; i += 1)
System.out.print(a[i] + " ");
return;
}
// left[i] stores the maximum value to left of i in the current block
// right[i] stores the maximum value to the right of i in the current block
int left[] = new int[n];
int right[] = new int[n];
for (int i = 0; i < n; i++)
{
// if the element is starting element of that block
if (i % k == 0)
left[i] = a[i];
else
left[i] = Math.max(left[i - 1], a[i]);
// if the element is ending element of that block
if ((n - i) % k == 0 || i == 0)
right[n - 1 - i] = a[n - 1 - i];
else
right[n - 1 - i] = Math.max(right[n - i], a[n - 1 - i]);
}
for (int i = 0, j = k - 1; j < n; i++, j++)
System.out.print(Math.max(left[j], right[i]) + " ");
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int n = a.length;
int K = 3;
printKMax(a, n, K);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 program to find the maximum for each # and every contiguous subarray of size K # Function to find the maximum for each # and every contiguous subarray of size k def printKMax(a, n, k): # If k = 1, print all elements if (k == 1): for i in range(n): print(a[i],end = " ") return # left[i] stores the maximum value to left of i in the current block # right[i] stores the maximum value to the right of i in the current block left = [ 0 for i in range(n)] right = [ 0 for i in range(n)] for i in range(n): # if the element is starting element of that block if (i % k == 0): left[i] = a[i] else: left[i] = max(left[i - 1], a[i]) # if the element is ending element of that block if ((n - i) % k == 0 or i == 0): right[n - 1 - i] = a[n - 1 - i] else: right[n - 1 - i] = max(right[n - i], a[n - 1 - i]) i = 0 j = k - 1 while j < n: print(max(left[j], right[i]),end = " ") i += 1 j += 1 # Driver Code a = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] n = len(a) K = 3 printKMax(a, n, K) # This code is contributed by shinjanpatra
C#
// C# program to find the maximum for each
// and every contiguous subarray of size K
using System;
class GFG
{
// Function to find the maximum for each
// and every contiguous subarray of size k
static void printKMax(int []a, int n, int k)
{
// If k = 1, print all elements
if (k == 1) {
for (int i = 0; i < n; i += 1)
Console.Write(a[i] + " ");
return;
}
// left[i] stores the maximum value to left of i in the current block
// right[i] stores the maximum value to the right of i in the current block
int []left = new int[n];
int []right = new int[n];
for (int i = 0; i < n; i++)
{
// if the element is starting element of that block
if (i % k == 0)
left[i] = a[i];
else
left[i] = Math.Max(left[i - 1], a[i]);
// if the element is ending element of that block
if ((n - i) % k == 0 || i == 0)
right[n - 1 - i] = a[n - 1 - i];
else
right[n - 1 - i] = Math.Max(right[n - i], a[n - 1 - i]);
}
for (int i = 0, j = k - 1; j < n; i++, j++)
Console.Write(Math.Max(left[j], right[i]) + " ");
}
// Driver Code
public static void Main(String[] args)
{
int []a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int n = a.Length;
int K = 3;
printKMax(a, n, K);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript program to find the maximum for each
// and every contiguous subarray of size K
// Function to find the maximum for each
// and every contiguous subarray of size k
function printKMax(a, n, k)
{
// If k = 1, print all elements
if (k == 1) {
for (var i = 0; i < n; i += 1)
document.write(a[i] + " ");
return;
}
// left[i] stores the maximum value to left of i in the current block
// right[i] stores the maximum value to the right of i in the current block
var left = [n];
var right = [n];
for (var i = 0; i < n; i++)
{
// if the element is starting element of that block
if (i % k == 0)
left[i] = a[i];
else
left[i] = Math.max(left[i - 1], a[i]);
// if the element is ending element of that block
if ((n - i) % k == 0 || i == 0)
right[n - 1 - i] = a[n - 1 - i];
else
right[n - 1 - i] = Math.max(right[n - i], a[n - 1 - i]);
}
for (var i = 0, j = k - 1; j < n; i++, j++)
document.write(Math.max(left[j], right[i]) + " ");
}
// Driver Code
var a = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
var n = a.length;
var K = 3;
printKMax(a, n, K);
// This code is contributed by shivanisinghss2110
</script>
Producción
3 4 5 6 7 8 9 10
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(n)
Publicación traducida automáticamente
Artículo escrito por yashbeersingh42 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA