Рубрики

Найти максимум минимума для каждого размера окна в данном массиве

Учитывая целочисленный массив размера n, найдите максимум минимумов каждого размера окна в массиве. Обратите внимание, что размер окна варьируется от 1 до n.

Пример:

Input:  arr[] = {10, 20, 30, 50, 10, 70, 30}
Output:         70, 30, 20, 10, 10, 10, 10

First element in output indicates maximum of minimums of all 
windows of size 1.
Minimums of windows of size 1 are {10}, {20}, {30}, {50}, {10},
{70} and {30}.  Maximum of these minimums is 70

Second element in output indicates maximum of minimums of all 
windows of size 2.
Minimums of windows of size 2 are {10}, {20}, {30}, {10}, {10},
and {30}.  Maximum of these minimums is 30

Third element in output indicates maximum of minimums of all 
windows of size 3.
Minimums of windows of size 3 are {10}, {20}, {10}, {10} and {10}. 
Maximum of these minimums is 20

Similarly other elements of output are computed.

Простое решение — пройти через все окна любого размера, найти максимум всех окон. Ниже приведена реализация этой идеи.

C ++

// Наивный метод, чтобы найти максимум минимума всех окон
// разных размеров
#include <iostream>
#include <climits>

using namespace std;

  

void printMaxOfMin(int arr[], int n)

{

    // Рассмотрим все окна разных размеров, начиная

    // с размера 1

    for (int k=1; k<=n; k++)

    {

        // Инициализируем max of min для текущего размера окна k

        int maxOfMin = INT_MIN;

  

        // Обход всех окон текущего размера k

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

        {

            // Находим минимум текущего окна

            int min = arr[i];

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

            {

                if (arr[i+j] < min)

                    min = arr[i+j];

            }

  

            // Обновляем maxOfMin, если требуется

            if (min > maxOfMin)

              maxOfMin = min;

        }

  

        // Выводим максимум мин для текущего размера окна

        cout << maxOfMin << " ";

    }

}

  
// Драйвер программы

int main()

{

    int arr[] = {10, 20, 30, 50, 10, 70, 30};

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

    printMaxOfMin(arr, n);

    return 0;

}

Джава

// Наивный метод, чтобы найти максимум минимума всех окон
// разных размеров

  

class Test

{

    static int arr[] = {10, 20, 30, 50, 10, 70, 30};

      

    static void printMaxOfMin(int n)

    {

        // Рассмотрим все окна разных размеров, начиная

        // с размера 1

        for (int k=1; k<=n; k++)

        {

            // Инициализируем max of min для текущего размера окна k

            int maxOfMin = Integer.MIN_VALUE;

       

            // Обход всех окон текущего размера k

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

            {

                // Находим минимум текущего окна

                int min = arr[i];

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

                {

                    if (arr[i+j] < min)

                        min = arr[i+j];

                }

       

                // Обновляем maxOfMin, если требуется

                if (min > maxOfMin)

                  maxOfMin = min;

            }

       

            // Выводим максимум мин для текущего размера окна

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

        }

    }

      

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

    public static void main(String[] args) 

    {

        printMaxOfMin(arr.length);

    }

}

python3

# Наивный метод, чтобы найти максимум
# минимум всех окон разных размеров

INT_MIN = -1000000

def printMaxOfMin(arr, n): 

      

    # Рассмотрим все окна разных

    # размеры начиная с размера 1

    for k in range(1, n + 1): 

          

        # Инициализировать максимум мин для

        # текущий размер окна k

        maxOfMin = INT_MIN; 

  

        # Пройдите через все окна

        # текущего размера k

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

              

            # Найти минимум текущего окна

            min = arr[i] 

            for j in range(k): 

                if (arr[i + j] < min): 

                    min = arr[i + j]

  

            # Обновите maxOfMin, если требуется

            if (min > maxOfMin): 

                maxOfMin = min

                  

        # Напечатать максимум мин для текущего размера окна

        print(maxOfMin, end = " ")

  
Код водителя

arr = [10, 20, 30, 50, 10, 70, 30

n = len(arr)

printMaxOfMin(arr, n)

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

C #

// C # программа, использующая наивный подход для поиска
// максимум минимума всех окон
// разных размеров

using System;

  

class GFG{

      

    static int []arr = {10, 20, 30, 50, 10, 70, 30};

      

    // Функция для печати максимума минимума

    static void printMaxOfMin(int n)

    {

          

        // Рассмотрим все окна разных

        // размеры начиная с размера 1

        for (int k = 1; k <= n; k++)

        {

              

            // Инициализируем максимум мин для

            // текущий размер окна k

            int maxOfMin = int.MinValue;

      

            // Обход всех окон

            // текущего размера k

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

            {

                  

                // Находим минимум текущего окна

                int min = arr[i];

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

                {

                    if (arr[i + j] < min)

                        min = arr[i + j];

                }

      

                // Обновляем maxOfMin, если требуется

                if (min > maxOfMin)

                    maxOfMin = min;

            }

      

            // Выводим максимум мин для текущего размера окна

            Console.Write(maxOfMin + " ");

        }

    }

      

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

    public static void Main() 

    {

        printMaxOfMin(arr.Length);

    }

}

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

PHP

<?php
// PHP программа для поиска максимума
// минимум всех окон
// разных размеров

  
// Метод, чтобы найти максимум
// минимум всех окон
// разных размеров

function printMaxOfMin($arr, $n)

{

      

    // Рассмотрим все окна

    // разные размеры начиная

    // с размера 1

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

    {

          

        // Инициализируем максимум мин для

        // текущий размер окна k

        $maxOfMin = PHP_INT_MIN;

  

        // Обход всех окон

        // текущего размера k

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

        {

              

            // Находим минимум текущего окна

            $min = $arr[$i];

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

            {

                if ($arr[$i + $j] < $min)

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

            }

  

            // Обновляем maxOfMin

            // если необходимо

            if ($min > $maxOfMin)

            $maxOfMin = $min;

        }

  

        // Выводим максимум мин для

        // текущий размер окна

        echo $maxOfMin , " ";

    }

}

  

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

    $arr= array(10, 20, 30, 50, 10, 70, 30);

    $n = sizeof($arr);

    printMaxOfMin($arr, $n);

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

Выход:

70 30 20 10 10 10 10

Временная сложность вышеуказанного решения может быть ограничена сверху O (n 3 ).

Мы можем решить эту проблему за O (n) время, используя Эффективное Решение . Идея состоит в том, чтобы использовать дополнительное пространство. Ниже приведены подробные шаги.
Шаг 1: Найти индексы следующего меньшего и предыдущего меньшего для каждого элемента. Следующим меньшим является ближайший наименьший элемент в правой части arr [i]. Точно так же предыдущий меньший элемент является ближайшим наименьшим элементом в левой части arr [i].
Если на правой стороне нет меньшего элемента, то следующим меньшим является n.Если на левой стороне нет меньшего, тогда предыдущим меньшим является -1.

Для ввода {10, 20, 30, 50, 10, 70, 30} массив индексов следующего меньшего равен {7, 4, 4, 4, 7, 6, 7}.
Для ввода {10, 20, 30, 50, 10, 70, 30}, массив индексов предыдущего меньшего равен {-1, 0, 1, 2, -1, 4, 4}

Этот шаг может быть выполнен за O (n) время с использованием подхода, обсужденного в следующем более крупном элементе .

Шаг 2: Когда у нас есть индексы следующего и предыдущего меньшего размера, мы знаем, что arr [i] является минимумом окна длины «right [i] — left [i] — 1». Длина окон, для которых элементы минимальны, составляет {7, 3, 2, 1, 7, 1, 2}. Этот массив указывает, что первый элемент является минимальным в окне размера 7, второй элемент является минимальным в окне размера 3 и так далее.

Создайте вспомогательный массив ans [n + 1] для хранения результата. Значения в ans [] можно заполнить, просматривая right [] и left []

    for (int i=0; i < n; i++)
    {
        // length of the interval
        int len = right[i] - left[i] - 1;

        // a[i] is the possible answer for
        // this length len interval
        ans[len] = max(ans[len], arr[i]);
    }

Мы получаем массив ans [] как {0, 70, 30, 20, 0, 0, 0, 10}. Обратите внимание, что ans [0] или ответ для длины 0 бесполезен.

Шаг 3: Некоторые записи в ans [] равны 0 и еще не заполнены. Например, мы знаем, что максимум минимума для длин 1, 2, 3 и 7 равен 70, 30, 20 и 10 соответственно, но мы не знаем того же для длин 4, 5 и 6.
Ниже приведено несколько важных замечаний для заполнения оставшихся записей.
a) Результат для длины i, т. е. ans [i] всегда будет больше или равен результату для длины i + 1, т. е. ans [i + 1].
б) Если ans [i] не заполнен, это означает, что не существует прямого элемента, который имеет минимальную длину i и, следовательно, либо элемент длины ans [i + 1], либо ans [i + 2] и т. д. является тем же как и я
Таким образом, мы заполняем остальные записи, используя цикл ниже.

    for (int i=n-1; i>=1; i--)
        ans[i] = max(ans[i], ans[i+1]);

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

C ++

// Эффективная программа на C ++ для нахождения максимума всех минимумов
// окна разных размеров
#include <iostream>
#include<stack>

using namespace std;

  

void printMaxOfMin(int arr[], int n)

{

    stack<int> s; // Используется для поиска предыдущего и следующего меньшего

  

    // Массивы для хранения предыдущего и следующего меньшего

    int left[n+1];  

    int right[n+1]; 

  

    // Инициализируем элементы left [] и right []

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

    {

        left[i] = -1;

        right[i] = n;

    }

  

    // Заполняем элементы left [] используя логику, обсуждаемую

    // https://www.geeksforgeeks.org/next-greater-element/amp/

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

    {

        while (!s.empty() && arr[s.top()] >= arr[i])

            s.pop();

  

        if (!s.empty())

            left[i] = s.top();

  

        s.push(i);

    }

  

    // Очистить стек, так как стек будет использоваться для right []

    while (!s.empty())

        s.pop();

  

    // Заполняем элементы right [] используя ту же логику

    for (int i = n-1 ; i>=0 ; i-- )

    {

        while (!s.empty() && arr[s.top()] >= arr[i])

            s.pop();

  

        if(!s.empty())

            right[i] = s.top();

  

        s.push(i);

    }

  

    // Создать и инициализировать массив ответов

    int ans[n+1];

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

        ans[i] = 0;

  

    // Заполняем массив ответов, сравнивая минимумы всех

    // длины, вычисленные с использованием left [] и right []

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

    {

        // длина интервала

        int len = right[i] - left[i] - 1;

  

        // arr [i] - возможный ответ для этой длины

        // интервал 'len', проверяем, больше ли arr [i]

        // максимум для 'len'

        ans[len] = max(ans[len], arr[i]);

    }

  

    // Некоторые записи в ans [] могут быть еще не заполнены. Заливка

    // их, взяв значения из правой части ans []

    for (int i=n-1; i>=1; i--)

        ans[i] = max(ans[i], ans[i+1]);

  

    // Распечатать результат

    for (int i=1; i<=n; i++)

        cout << ans[i] << " ";

}

  
// Драйвер программы

int main()

{

    int arr[] = {10, 20, 30, 50, 10, 70, 30};

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

    printMaxOfMin(arr, n);

    return 0;

}

Джава

// Эффективная Java-программа для поиска максимума всех минимумов
// окна разного размера

  

import java.util.Stack;

  

class Test

{

    static int arr[] = {10, 20, 30, 50, 10, 70, 30};

      

    static void printMaxOfMin(int n)

    {

        // Используется для поиска предыдущего и следующего меньшего

        Stack<Integer> s = new Stack<>();

       

        // Массивы для хранения предыдущего и следующего меньшего

        int left[] = new int[n+1];  

        int right[]  = new int[n+1]; 

       

        // Инициализируем элементы left [] и right []

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

        {

            left[i] = -1;

            right[i] = n;

        }

       

        // Заполняем элементы left [] используя логику, обсуждаемую

        // https://www.geeksforgeeks.org/next-greater-element/amp/

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

        {

            while (!s.empty() && arr[s.peek()] >= arr[i])

                s.pop();

       

            if (!s.empty())

                left[i] = s.peek();

       

            s.push(i);

        }

       

        // Очистить стек, так как стек будет использоваться для right []

        while (!s.empty())

            s.pop();

       

        // Заполняем элементы right [] используя ту же логику

        for (int i = n-1 ; i>=0 ; i-- )

        {

            while (!s.empty() && arr[s.peek()] >= arr[i])

                s.pop();

       

            if(!s.empty())

                right[i] = s.peek();

       

            s.push(i);

        }

       

        // Создать и инициализировать массив ответов

        int ans[] = new int[n+1];

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

            ans[i] = 0;

       

        // Заполняем массив ответов, сравнивая минимумы всех

        // длины, вычисленные с использованием left [] и right []

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

        {

            // длина интервала

            int len = right[i] - left[i] - 1;

       

            // arr [i] - возможный ответ для этой длины

            // интервал 'len', проверяем, больше ли arr [i]

            // максимум для 'len'

            ans[len] = Math.max(ans[len], arr[i]);

        }

       

        // Некоторые записи в ans [] могут быть еще не заполнены. Заливка

        // их, взяв значения из правой части ans []

        for (int i=n-1; i>=1; i--)

            ans[i] = Math.max(ans[i], ans[i+1]);

       

        // Распечатать результат

        for (int i=1; i<=n; i++)

            System.out.print(ans[i] + " ");

    }

      

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

    public static void main(String[] args) 

    {

        printMaxOfMin(arr.length);

    }

}

python3

# Эффективная программа Python3 для поиска
# максимум всех минимумов окон
# разных размеров

  

def printMaxOfMin(arr, n):

      

    s = [] # Используется для поиска предыдущего

           # и следующий меньше

  

    # Массивы для хранения предыдущего и следующего

    # меньше. Инициализировать элементы

    # Лево и право[]

    left = [-1] * (n + 1

    right = [n] * (n + 1

  

    # Заполните элементы left [], используя логику, обсуждаемую

    # https: # www.geeksforgeeks.org / next-большее-элемент

    for i in range(n):

        while (len(s) != 0 and 

               arr[s[-1]] >= arr[i]): 

            s.pop() 

  

        if (len(s) != 0):

            left[i] = s[-1]

  

        s.append(i)

  

    # Очистить стек по мере загрузки

    # будет использоваться для права []

    while (len(s) != 0):

        s.pop()

  

    # Заполните элементы right [], используя ту же логику

    for i in range(n - 1, -1, -1):

        while (len(s) != 0 and arr[s[-1]] >= arr[i]): 

            s.pop() 

  

        if(len(s) != 0): 

            right[i] = s[-1

  

        s.append(i)

  

    # Создать и инициализировать массив ответов

    ans = [0] * (n + 1)

    for i in range(n + 1):

        ans[i] = 0

  

    # Заполните массив ответов, сравнив минимумы

    # из всех. Длина рассчитывается с использованием левой []

    # и справа []

    for i in range(n):

          

        # Длина интервала

        Len = right[i] - left[i] - 1

  

        # arr [i] является возможным ответом на это

        # Длина интервала 'Len', проверьте, если arr [i]

        # больше чем максимум для 'Len'

        ans[Len] = max(ans[Len], arr[i])

  

    # Некоторые записи в ans [] могут быть не заполнены

    # еще. Заполните их, взяв значения из

    # правая сторона ответа []

    for i in range(n - 1, 0, -1):

        ans[i] = max(ans[i], ans[i + 1]) 

  

    # Распечатать результат

    for i in range(1, n + 1):

        print(ans[i], end = " ")

  
Код водителя

if __name__ == '__main__':

  

    arr = [10, 20, 30, 50, 10, 70, 30

    n = len(arr) 

    printMaxOfMin(arr, n)

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

C #

// Эффективная программа на C # для поиска максимума
// всех минимумов окон разного размера

using System;

using System.Collections.Generic;

  

class GFG

{

public static int[] arr = new int[] {10, 20, 30, 50,

                                     10, 70, 30};

  

public static void printMaxOfMin(int n)

{

    // Используется для поиска предыдущего и следующего меньшего

    Stack<int> s = new Stack<int>();

  

    // Массивы для хранения предыдущего

    // и следующий меньше

    int[] left = new int[n + 1];

    int[] right = new int[n + 1];

  

    // Инициализируем элементы left []

    // и вправо []

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

    {

        left[i] = -1;

        right[i] = n;

    }

  

    // Заполняем элементы left [] используя логику, обсуждаемую

    // https://www.geeksforgeeks.org/next-greater-element/amp/

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

    {

        while (s.Count > 0 && 

               arr[s.Peek()] >= arr[i])

        {

            s.Pop();

        }

  

        if (s.Count > 0)

        {

            left[i] = s.Peek();

        }

  

        s.Push(i);

    }

  

    // Очистить стек по мере его поступления

    // для правого использования []

    while (s.Count > 0)

    {

        s.Pop();

    }

  

    // Заполняем элементы right [] используя

    // та же логика

    for (int i = n - 1 ; i >= 0 ; i--)

    {

        while (s.Count > 0 && 

               arr[s.Peek()] >= arr[i])

        {

            s.Pop();

        }

  

        if (s.Count > 0)

        {

            right[i] = s.Peek();

        }

  

        s.Push(i);

    }

  

    // Создать и инициализировать массив ответов

    int[] ans = new int[n + 1];

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

    {

        ans[i] = 0;

    }

  

    // Заполняем массив ответов, сравнивая

    // минимумы всех вычисленных длин

    // используя left [] и right []

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

    {

        // длина интервала

        int len = right[i] - left[i] - 1;

  

        // arr [i] - возможный ответ для

        // эта длина 'len' интервал, проверка x

        // если arr [i] больше max для 'len'

        ans[len] = Math.Max(ans[len], arr[i]);

    }

  

    // Некоторые записи в ans [] могут не быть

    // заполнено еще. Заполните их, взяв

    // значения справа от ans []

    for (int i = n - 1; i >= 1; i--)

    {

        ans[i] = Math.Max(ans[i], ans[i + 1]);

    }

  

    // Распечатать результат

    for (int i = 1; i <= n; i++)

    {

        Console.Write(ans[i] + " ");

    }

}

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

public static void Main(string[] args)

{

    printMaxOfMin(arr.Length);

}
}

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

Выход:

70 30 20 10 10 10 10

Сложность времени: O (n)
Вспомогательное пространство: O (n)

Эта статья предоставлена Эктой Гоэль и Аюшем Говилом . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Найти максимум минимума для каждого размера окна в данном массиве

0.00 (0%) 0 votes