Рубрики

Самая большая прямоугольная область в гистограмме | Набор 2

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

Например, рассмотрим следующую гистограмму с 7 столбиками высоты {6, 2, 5, 4, 5, 1, 6}. Максимально возможный прямоугольник — 12 (см. Рисунок ниже, прямоугольник максимальной площади выделен красным цветом)

Мы обсудили решение этой проблемы на основе O (nLogn) на основе «разделяй и властвуй» . В этом посте обсуждается время решения O (n). Как и в предыдущем посте , ширина всех баров для простоты принимается равной 1. Для каждого бара «х» мы вычисляем площадь с «х» в качестве наименьшего бара в прямоугольнике. Если мы вычислим такую площадь для каждого бара 'x' и найдем максимум всех областей, наша задача будет выполнена. Как рассчитать площадь с 'х', как наименьший бар? Нам нужно знать индекс первого меньшего (меньше чем x) бара слева от «x» и индекс первого меньшего бара справа от «x». Давайте назовем эти индексы как «левый индекс» и «правый индекс» соответственно.
Мы пересекаем все бары слева направо, сохраняем стек баров. Каждый бар ставится в стек один раз. Стержень выталкивается из стопки, когда видна полоса меньшей высоты. Когда столбик выталкивается, мы вычисляем площадь с вытянутым стержнем как наименьший столбец. Как мы получаем левый и правый индексы вытолкнутого бара — текущий индекс говорит нам о «правом индексе», а индекс предыдущего элемента в стеке — это «левый индекс». Ниже приводится полный алгоритм.

1) Создайте пустой стек.

2) Начните с первого бара и следуйте за каждым баром 'hist [i]', где 'i' изменяется от 0 до n-1.
…… а) Если стек пуст или исторических [i] выше, чем бар на вершине стека, нажмите «i» в стеке.
…… б) Если этот столбец меньше вершины стека, то продолжайте удалять вершину стека, пока вершина стека больше. Пусть удаленный бар будет историческим [tp]. Вычислить площадь прямоугольника с историей [tp] в качестве наименьшего столбца. Для исторических [tp] «левый индекс» является предыдущим (предшествующим tp) элементом в стеке, а «правый индекс» — «i» (текущий индекс).

3) Если стек не пуст, то один за другим удалите все столбцы из стека и выполните шаг 2.b для каждого удаленного столбца.

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

C ++

// C ++ программа для поиска максимальной прямоугольной области в
// линейное время
#include<iostream>
#include<stack>

using namespace std;

  
// Основная функция для нахождения максимального прямоугольника
// область под данной гистограммой с n столбцами

int getMaxArea(int hist[], int n)

{

    // Создать пустой стек. Стек содержит индексы

    // массива исторических []. Бары хранятся в стеке

    // всегда в порядке возрастания их высоты.

    stack<int> s;

  

    int max_area = 0; // Инициализируем максимальную площадь

    int tp;  // Для хранения вершины стека

    int area_with_top; // Для хранения области с верхней панелью

                       // как самый маленький бар

  

    // Пройти через все бары данной гистограммы

    int i = 0;

    while (i < n)

    {

        // Если этот бар выше, чем бар сверху

        // укладываем, помещаем в стек

        if (s.empty() || hist[s.top()] <= hist[i])

            s.push(i++);

  

        // Если этот бар ниже вершины стека,

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

        // top как самая маленькая (или минимальная высота) полоса.

        // 'i' - это 'правильный индекс' для вершины и элемента

        // перед вершиной в стеке есть «левый индекс»

        else

        {

            tp = s.top();  // сохраняем верхний индекс

            s.pop();  // поп топ

  

            // Вычисляем площадь с помощью стека исторических [tp]

            // как самый маленький бар

            area_with_top = hist[tp] * (s.empty() ? i : 

                                   i - s.top() - 1);

  

            // обновить максимальную площадь, если необходимо

            if (max_area < area_with_top)

                max_area = area_with_top;

        }

    }

  

    // Теперь вытолкните оставшиеся бары из стека и вычислите

    // область с каждым вытянутым столбцом в качестве наименьшего столбца

    while (s.empty() == false)

    {

        tp = s.top();

        s.pop();

        area_with_top = hist[tp] * (s.empty() ? i : 

                                i - s.top() - 1);

  

        if (max_area < area_with_top)

            max_area = area_with_top;

    }

  

    return max_area;

}

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

int main()

{

    int hist[] = {6, 2, 5, 4, 5, 1, 6};

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

    cout << "Maximum area is " << getMaxArea(hist, n);

    return 0;

}

Джава

// Java-программа для поиска максимальной прямоугольной области за линейное время

  

import java.util.Stack;

  

public class RectArea 

{

    // Основная функция для нахождения максимальной прямоугольной области под заданной

    // гистограмма с n столбцами

    static int getMaxArea(int hist[], int n) 

    {

        // Создать пустой стек. В стеке хранятся индексы массива hist []

        // Бары, хранящиеся в стеке, всегда в порядке возрастания

        // высоты.

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

          

        int max_area = 0; // Инициализируем максимальную площадь

        int tp;  // Для хранения вершины стека

        int area_with_top; // Сохранить область с верхним баром как наименьший бар

       

        // Пройти через все бары данной гистограммы

        int i = 0;

        while (i < n)

        {

            // Если этот бар выше, чем бар в верхнем стеке, поместите его в стек

            if (s.empty() || hist[s.peek()] <= hist[i])

                s.push(i++);

       

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

            // с верхом стека в качестве наименьшей (или минимальной высоты) полосы. «Я» это

            // «правый индекс» для вершины и элемента перед вершиной в стеке - «левый индекс»

            else

            {

                tp = s.peek();  // сохраняем верхний индекс

                s.pop();  // поп топ

       

                // Рассчитать область с историческим стеком [tp] как наименьшим баром

                area_with_top = hist[tp] * (s.empty() ? i : i - s.peek() - 1);

       

                // обновить максимальную площадь, если необходимо

                if (max_area < area_with_top)

                    max_area = area_with_top;

            }

        }

       

        // Теперь выталкиваем оставшиеся бары из стека и вычисляем площадь с каждым

        // выскочил бар как самый маленький бар

        while (s.empty() == false)

        {

            tp = s.peek();

            s.pop();

            area_with_top = hist[tp] * (s.empty() ? i : i - s.peek() - 1);

       

            if (max_area < area_with_top)

                max_area = area_with_top;

        }

       

        return max_area;

  

    }

      

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

    public static void main(String[] args) 

    {

        int hist[] = { 6, 2, 5, 4, 5, 1, 6 };

        System.out.println("Maximum area is " + getMaxArea(hist, hist.length));

    }

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

python3

# Python3 программа для поиска максимума
# прямоугольная область в линейном времени

  

def max_area_histogram(histogram):

      

    # Эта функция рассчитывает максимум

    # прямоугольная область под данным

    # гистограмма с n столбцами

  

    # Создать пустой стек. Стек

    # содержит индексы списка гистограмм [].

    # Бары хранятся в стеке

    # всегда в порядке возрастания

    # их высоты.

    stack = list()

  

    max_area = 0 # Инициализировать максимальную площадь

  

    # Пробежать все бары

    # заданная гистограмма

    index = 0

    while index < len(histogram):

          

        # Если этот бар выше

        # чем бар сверху

        # стек, переместите его в стек

  

        if (not stack) or (histogram[stack[-1]] <= histogram[index]):

            stack.append(index)

            index += 1

  

        # Если этот бар ниже вершины стека,

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

        # вершина стека как наименьшая (или минимальная

        # height) bar.'i 'это' правильный индекс 'для

        # вершина и элемент перед вершиной в стеке

        # это «левый индекс»

        else:

            # поп топ

            top_of_stack = stack.pop()

  

            # Рассчитать площадь с

            # гистограмма [top_of_stack] стек

            # как самый маленький бар

            area = (histogram[top_of_stack] * 

                   ((index - stack[-1] - 1

                   if stack else index))

  

            # обновить максимальную площадь, если необходимо

            max_area = max(max_area, area)

  

    # Теперь вытолкните оставшиеся бары из

    # складывать и вычислять площадь с

    # каждый всплывающий столбец как самый маленький столбец

    while stack:

          

        # поп топ

        top_of_stack = stack.pop()

  

        # Рассчитать площадь с

        # гистограмма [top_of_stack]

        # стек как наименьший бар

        area = (histogram[top_of_stack] * 

              ((index - stack[-1] - 1

                if stack else index))

  

        # обновить максимальную площадь, если необходимо

        max_area = max(max_area, area)

  

    # Вернуть максимальную площадь под

    # данная гистограмма

    return max_area

  
Код водителя

hist = [6, 2, 5, 4, 5, 1, 6]

print("Maximum area is"

       max_area_histogram(hist))

  
# Этот код добавлен
# Джинай Шах

C #

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

using System;

using System.Collections.Generic;

  

class GFG

{
// Основная функция для поиска
// максимальная прямоугольная площадь под
// заданная гистограмма с n столбцами

public static int getMaxArea(int[] hist,

                             int n)

{

    // Создать пустой стек. Стек

    // содержит индексы массива hist []

    // Бары хранятся в стеке всегда

    // в порядке возрастания их высот.

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

  

    int max_area = 0; // Инициализируем максимальную площадь

    int tp; // Для хранения вершины стека

    int area_with_top; // Для хранения области с верхом

                       // бар как самый маленький бар

  

    // Пробежаться по всем барам

    // заданная гистограмма

    int i = 0;

    while (i < n)

    {

        // Если этот бар выше чем

        // бар на верхнем стеке, толкаем его в стек

        if (s.Count == 0 || hist[s.Peek()] <= hist[i])

        {

            s.Push(i++);

        }

  

        // Если этот бар ниже вершины стека,

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

        // складываем вершину как наименьшее (или минимальное

        // высота) бар. «Я» является «правильный индекс» для

        // вершина и элемент перед вершиной в стеке

        // это «левый индекс»

        else

        {

            tp = s.Peek(); // сохраняем верхний индекс

            s.Pop(); // поп топ

  

            // Рассчитать площадь с помощью исторических [tp]

            // укладываем как наименьший бар

            area_with_top = hist[tp] * 

                           (s.Count == 0 ? i : i - s.Peek() - 1);

  

            // обновить максимальную площадь, если необходимо

            if (max_area < area_with_top)

            {

                max_area = area_with_top;

            }

        }

    }

  

    // Теперь выталкиваем оставшиеся бары из

    // складываем и вычисляем площадь с каждым

    // выскочил бар как самый маленький бар

    while (s.Count > 0)

    {

        tp = s.Peek();

        s.Pop();

        area_with_top = hist[tp] * 

                       (s.Count == 0 ? i : i - s.Peek() - 1);

  

        if (max_area < area_with_top)

        {

            max_area = area_with_top;

        }

    }

  

    return max_area;

  
}

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

public static void Main(string[] args)

{

    int[] hist = new int[] {6, 2, 5, 4, 5, 1, 6};

    Console.WriteLine("Maximum area is "

                       getMaxArea(hist, hist.Length));

}
}

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

Выход:

Maximum area is 12

Сложность времени: так как каждый бар толкается и выталкивается только один раз, временная сложность этого метода составляет O (n).

Ссылки
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/histogram.html
http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html

Благодаря Ashish Anand за предположение первоначального решения. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Самая большая прямоугольная область в гистограмме | Набор 2

0.00 (0%) 0 votes