Рубрики

Максимум скользящего окна (максимум всех подмассивов размера k)

Для данного массива и целого числа K найдите максимум для каждого смежного подмассива размера k.

Примеры :

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

Input: arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, K = 4
Output: 10 10 10 15 15 90 90

Способ 1 (простой)
Запустите две петли. Во внешнем цикле возьмите все подмассивы размера K. Во внутреннем цикле получите максимум текущего подмассива.

C ++

// C ++ Программа для поиска максимума для
// каждый смежный подмассив размера k.
#include <bits/stdc++.h>

using namespace std;

  
// Метод, чтобы найти максимум для каждого
// и каждый смежный подмассив размера k.

void printKMax(int arr[], int n, int k) 

    int j, max; 

  

    for (int i = 0; i <= n - k; i++) 

    

        max = arr[i]; 

  

        for (j = 1; j < k; j++) 

        

            if (arr[i + j] > max) 

                max = arr[i + j]; 

        

        cout << max << " "

    

  
// Код драйвера

int main() 

    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 

    int n = sizeof(arr) / sizeof(arr[0]); 

    int k = 3; 

    printKMax(arr, n, k); 

    return 0; 

}

  
// Этот код предоставлен rathbhupendra

С

#include <stdio.h>

  

void printKMax(int arr[], int n, int k)

{

    int j, max;

  

    for (int i = 0; i <= n - k; i++) {

        max = arr[i];

  

        for (j = 1; j < k; j++) {

            if (arr[i + j] > max)

                max = arr[i + j];

        }

        printf("%d ", max);

    }

}

  

int main()

{

    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

    int n = sizeof(arr) / sizeof(arr[0]);

    int k = 3;

    printKMax(arr, n, k);

    return 0;

}

Джава

// Java-программа, чтобы найти максимум для каждого смежного подмассива размера k.

  

public class GFG {

    // Метод, чтобы найти максимум для каждого смежного подмассива размера k.

    static void printKMax(int arr[], int n, int k)

    {

        int j, max;

  

        for (int i = 0; i <= n - k; i++) {

  

            max = arr[i];

  

            for (j = 1; j < k; j++) {

                if (arr[i + j] > max)

                    max = arr[i + j];

            }

            System.out.print(max + " ");

        }

    }

  

    // Метод драйвера

    public static void main(String args[])

    {

        int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        int k = 3;

        printKMax(arr, arr.length, k);

    }

}

  
// Этот код предоставлен Sumit Ghosh

python3

# Программа Python, чтобы найти максимум для
# каждый смежный подмассив
# размер к

  
# Способ найти максимум для каждого
# и каждый смежный подмассив s
№ размера к

def printMax(arr, n, k):

    max = 0

    

    for i in range(n - k + 1):

        max = arr[i]

        for j in range(1, k):

            if arr[i + j] > max:

                max = arr[i + j]

        print(str(max) + " ", end = "")

  
# Метод драйвера

if __name__=="__main__":

    arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

    n = len(arr)

    k = 3

    printMax(arr, n, k)

  
# Этот код предоставлен Shiv Shankar

C #

// C # программа для поиска максимума
// каждый смежный подмассив
// система размера размера;

using System;

  

class GFG {

    // Способ найти максимум для

    // каждый смежный подмассив

    // размера k.

    static void printKMax(int[] arr, int n, int k)

    {

        int j, max;

  

        for (int i = 0; i <= n - k; i++) {

  

            max = arr[i];

  

            for (j = 1; j < k; j++) {

                if (arr[i + j] > max)

                    max = arr[i + j];

            }

            Console.Write(max + " ");

        }

    }

  

    // Метод драйвера

    public static void Main()

    {

        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

        int k = 3;

        printKMax(arr, arr.Length, k);

    }

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для поиска максимума
// для каждого смежного
// подрешетка размера k

  

function printKMax($arr, $n, $k)

{

    $j; $max;

  

    for ($i = 0; $i <= $n - $k; $i++)

    {

        $max = $arr[$i];

  

        for ($j = 1; $j < $k; $j++)

        {

            if ($arr[$i + $j] > $max)

            $max = $arr[$i + $j];

        }

        printf("%d ", $max);

    }

}

  
// Код драйвера

$arr = array(1, 2, 3, 4, 5, 

             6, 7, 8, 9, 10);

$n = count($arr);

$k = 3;

printKMax($arr, $n, $k);

  
// Этот код предоставлен anuj_67.
?>

Выход:

3 4 5 6 7 8 9 10

Сложность времени: внешний цикл выполняется n-k + 1 раз, а внутренний цикл выполняется k раз за каждую итерацию внешнего цикла. Таким образом, временная сложность равна O ((n-k + 1) * k), которая также может быть записана как O (N * K) .

Способ 2 (использовать самобалансирующийся BST)

  • Выберите первые k элементов и создайте Самобалансирующееся Двоичное дерево поиска (BST) размера k.
  • Запустите цикл для i = 0 до n — k
    1. Получить максимальный элемент из BST и распечатать его.
    2. Найдите arr [i] в BST и удалите его из BST.
    3. Вставьте arr [i + k] в BST.

Сложность времени : Сложность времени шага 1 — O (K * Log k). Сложность времени шагов 2 (a), 2 (b) и 2 (c) равна O (Logk). Поскольку шаги 2 (a), 2 (b) и 2 (c) находятся в цикле, который выполняется n-k + 1 раз, временная сложность полного алгоритма составляет O (kLogk + (n-k + 1) * Logk) который также может быть записан как O (N * Log k) .

Метод 3 (метод O (n) : используйте Deque) Мы создаем Deque , Qi емкости k, в котором хранятся только полезные элементы текущего окна из k элементов. Элемент полезен, если он находится в текущем окне и больше, чем все остальные элементы слева от него в текущем окне. Мы обрабатываем все элементы массива один за другим и поддерживаем Qi, чтобы он содержал полезные элементы текущего окна, и эти полезные элементы поддерживаются в отсортированном порядке. Элемент в передней части ци является самым большим, а элемент в задней части ци является наименьшим из текущего окна. Спасибо Aashish за предложение этого метода.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода.

C ++

#include <deque>
#include <iostream>

  

using namespace std;

  
// Метод Dequeue (двусторонняя очередь) для печати максимального элемента
// все подмассивы размера k

void printKMax(int arr[], int n, int k)

{

    // Создать двойную очередь Qi, в которой будут храниться индексы элементов массива

    // Очередь будет хранить индексы полезных элементов в каждом окне и будет

    // поддерживать убывающий порядок значений спереди назад в Qi, т.е.

    // arr [Qi.front []] в arr [Qi.rear ()] отсортированы в порядке убывания

    std::deque<int> Qi(k);

  

    / * Обработка первых k (или первого окна) элементов массива * /

    int i;

    for (i = 0; i < k; ++i) {

        // Для каждого элемента предыдущие меньшие элементы бесполезны, поэтому

        // удаляем их из Ци

        while ((!Qi.empty()) && arr[i] >= arr[Qi.back()])

            Qi.pop_back(); // Удалить сзади

  

        // Добавить новый элемент в конец очереди

        Qi.push_back(i);

    }

  

    // Обработка остальных элементов, т. Е. От arr [k] до arr [n-1]

    for (; i < n; ++i) {

        // Элемент в начале очереди является самым большим элементом

        // предыдущее окно, поэтому выводим его

        cout << arr[Qi.front()] << " ";

  

        // Удалить элементы, которые находятся вне этого окна

        while ((!Qi.empty()) && Qi.front() <= i - k)

            Qi.pop_front(); // Удалить из начала очереди

  

        // Удаляем все элементы меньше текущего

        // добавляемый элемент (удаляем ненужные элементы)

        while ((!Qi.empty()) && arr[i] >= arr[Qi.back()])

            Qi.pop_back();

  

        // Добавить текущий элемент в задней части ци

        Qi.push_back(i);

    }

  

    // Выводим максимальный элемент последнего окна

    cout << arr[Qi.front()];

}

  
// Программа драйвера для проверки вышеуказанных функций

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;

}

Джава

// Java-программа, чтобы найти максимум для
// каждый смежный подмассив размера k.

  

import java.util.Deque;

import java.util.LinkedList;

  

public class SlidingWindow {

  

    // Метод Dequeue (двусторонняя очередь) для печати максимального элемента

    // все подмассивы размера k

    static void printMax(int arr[], int n, int k)

    {

        // Создать двойную очередь Qi, в которой будут храниться индексы элементов массива

        // Очередь будет хранить индексы полезных элементов в каждом окне и будет

        // поддерживать убывающий порядок значений спереди назад в Qi, т.е.

        // arr [Qi.front []] в arr [Qi.rear ()] отсортированы в порядке убывания

        Deque<Integer> Qi = new LinkedList<Integer>();

  

        / * Обработка первых k (или первого окна) элементов массива * /

        int i;

        for (i = 0; i < k; ++i) {

            // Для каждого элемента предыдущие меньшие элементы бесполезны, поэтому

            // удаляем их из Ци

            while (!Qi.isEmpty() && arr[i] >= arr[Qi.peekLast()])

                Qi.removeLast(); // Удалить сзади

  

            // Добавить новый элемент в конец очереди

            Qi.addLast(i);

        }

  

        // Обработка остальных элементов, т. Е. От arr [k] до arr [n-1]

        for (; i < n; ++i) {

            // Элемент в начале очереди является самым большим элементом

            // предыдущее окно, поэтому выводим его

            System.out.print(arr[Qi.peek()] + " ");

  

            // Удалить элементы, которые находятся вне этого окна

            while ((!Qi.isEmpty()) && Qi.peek() <= i - k)

                Qi.removeFirst();

  

            // Удаляем все элементы меньше текущего

            // добавляемый элемент (удаляем ненужные элементы)

            while ((!Qi.isEmpty()) && arr[i] >= arr[Qi.peekLast()])

                Qi.removeLast();

  

            // Добавить текущий элемент в задней части ци

            Qi.addLast(i);

        }

  

        // Выводим максимальный элемент последнего окна

        System.out.print(arr[Qi.peek()]);

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args)

    {

        int arr[] = { 12, 1, 78, 90, 57, 89, 56 };

        int k = 3;

        printMax(arr, arr.length, k);

    }

}
// Этот код предоставлен Sumit Ghosh

python3

# Программа Python, чтобы найти максимум для
# каждый смежный подмассив
# размер к

  

from collections import deque

  
# Deque (двусторонняя очередь) на основе
# метод печати максимального элемента
# всех подмассивов размера k

def printMax(arr, n, k):

      

    "" "Создайте двустороннюю очередь, Ци, которая

    будет хранить индексы элементов массива.

    В очереди будут храниться полезные индексы

    элементы в каждом окне, и это будет

    поддерживать убывающий порядок значений от

    спереди назад в ци, то есть arr [Qi.front []]

    к arr [Qi.rear ()] сортируются по убыванию

    заказ"""

    Qi = deque()

      

    # Обработка первого k (или первого окна)

    # элементы массива

    for i in range(k):

        

        # Для каждого элемента предыдущего

        # меньшие элементы бесполезны

        # так удали их из ци

        while Qi and arr[i] >= arr[Qi[-1]] :

            Qi.pop()

          

        # Добавить новый элемент в конец очереди

        Qi.append(i);

          

    # Обработка остальных элементов, т.е.

    # от arr [k] до arr [n-1]

    for i in range(k, n):

          

        # Элемент в передней части

        # очередь является самым большим элементом

        # предыдущее окно, поэтому распечатайте его

        print(str(arr[Qi[0]]) + " ", end = "")

          

        # Удалить элементы, которые

        # из этого окна

        while Qi and Qi[0] <= i-k:

              

            # удалить с фронта deque

            Qi.popleft() 

          

        # Удалить все элементы меньше чем

        # добавляемый элемент

        # (Удалить ненужные элементы)

        while Qi and arr[i] >= arr[Qi[-1]] :

            Qi.pop()

          

        # Добавить текущий элемент в задней части ци

        Qi.append(i)

      

    # Вывести максимальный элемент последнего окна

    print(str(arr[Qi[0]]))

      
# Драйверная программа для проверки вышеуказанных функций

if __name__=="__main__":

    arr = [12, 1, 78, 90, 57, 89, 56]

    k = 3

    printMax(arr, len(arr), k)

      
# Этот код предоставлен Shiv Shankar

C #

// C # Программа для поиска максимума для каждого
// и каждый смежный подмассив размера k.

using System; 

using System.Collections.Generic;

  

public class SlidingWindow 

{

  

    // Dequeue (двусторонняя очередь) на основе

    // метод печати максимального элемента

    // все подмассивы размера k

    static void printMax(int []arr, int n, int k)

    {

        // Создать двойную очередь, Qi, которая

        // будем хранить индексы элементов массива

        // В очереди будут храниться полезные индексы

        // элементы в каждом окне, и это будет

        // поддерживать убывающий порядок значений

        // спереди назад в Ци, т.е.

        // arr [Qi.front []] в arr [Qi.rear ()]

        // отсортированы в порядке убывания

        List<int> Qi = new List<int>();

  

        / * Обработка первых k (или первого окна) элементов массива * /

        int i;

        for (i = 0; i < k; ++i) {

            // Для каждого элемента предыдущий

            // меньшие элементы бесполезны, так

            // удаляем их из Ци

            while (Qi.Count != 0 && arr[i] >= arr[Qi.IndexOf(0)])

                Qi.RemoveAt(Qi.Count-1); // Удалить сзади

  

            // Добавить новый элемент в конец очереди

            Qi.Insert(Qi.Count, i);

        }

  

        // Обработка остальных элементов,

        // то есть от arr [k] до arr [n-1]

        for (; i < n; ++i) 

        {

            // Элемент в начале

            // очередь является самым большим элементом

            // предыдущее окно, поэтому выводим его

            Console.Write(arr[Qi[0]] + " ");

  

            // Удалить элементы, которые находятся вне этого окна

            while ((Qi.Count != 0) && Qi[0] <= i - k)

                Qi.RemoveAt(0);

  

            // Удаляем все элементы меньше текущего

            // добавляемый элемент (удаляем ненужные элементы)

            while ((Qi.Count != 0) && arr[i] >= arr[Qi[Qi.Count - 1]])

                Qi.RemoveAt(Qi.Count - 1);

  

            // Добавить текущий элемент в задней части ци

            Qi.Insert(Qi.Count, i);

        }

  

        // Выводим максимальный элемент последнего окна

        Console.Write(arr[Qi[0]]);

    }

  

    // Код драйвера

    public static void Main(String[] args)

    {

        int []arr = { 12, 1, 78, 90, 57, 89, 56 };

        int k = 3;

        printMax(arr, arr.Length, k);

    }

}

  
// Этот код предоставлен 29AjayKumar

Выход:

78 90 90 90 89

Выход:

78 90 90 90 89

Ниже приведено расширение этой проблемы.
Сумма минимальных и максимальных элементов всех подмассивов размера k.

Сложность времени: O (n). На первый взгляд, это больше, чем O (n). Если мы посмотрим поближе, то увидим, что каждый элемент массива добавляется и удаляется не более одного раза. Таким образом, всего 2n операций.
Вспомогательное пространство: O (k)

Метод 4 (Использовать Max-Heap)

  1. Выберите первые k элементов и создайте максимальную кучу размером k.
  2. Выполните heapify и распечатайте корневой элемент.
  3. Сохранить следующий и последний элемент из массива
  4. Запустите цикл от k — 1 до n
    • Замените значение элемента, который выводится из окна, новым элементом, который появился внутри окна.
    • Выполните кучу.
    • Распечатайте корень кучи.

Сложность времени: Сложность времени шагов 4 (a) равна O (k), 4 (b) равна O (Log (k)), и она находится в цикле, который выполняется (n — k + 1) раз. Следовательно, временная сложность полного алгоритма составляет O ((k + Log (k)) * n), то есть O (n * k).

python3

# Программа Python, чтобы найти максимум для
# каждый смежный подмассив
# размер к

import heapq

  
# Способ найти максимум для каждого
# и каждый смежный подмассив s
№ размера к

def max_of_all_in_k(arr, n):

    i = 0

    j = k-1

      

    # Создайте кучу и сложите кучу

    heap = arr[i:j + 1]

    heapq._heapify_max(heap)

      

    # Вывести максимальный элемент из

    # первое окно размера k

    print(heap[0], end =" ")

    last = arr[i]

    i+= 1

    j+= 1

    nexts = arr[j]

      

    # Для каждого оставшегося элемента

    while j < n:

          

        # Добавить следующий элемент окна

        heap[heap.index(last)] = nexts

          

        # Heapify, чтобы получить максимум

        # текущего окна

        heapq._heapify_max(heap)

          

        # Распечатать текущий максимум

        print(heap[0], end =" ")

        last = arr[i]

        i+= 1

        j+= 1

        if j < n:

            nexts = arr[j]

              
# Функция драйвера

n, k = 10, 3

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

max_of_all_in_k(arr, n)

Выход:

3 4 5 6 7 8 9 10

Пожалуйста, напишите комментарии, если вы обнаружите, что приведенные выше коды / алгоритмы неверны, или найдете другие способы решения той же проблемы.

Рекомендуемые посты:

Максимум скользящего окна (максимум всех подмассивов размера k)

0.00 (0%) 0 votes