Рубрики

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

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

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

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

Мы можем использовать Divide and Conquer, чтобы решить это за O (nLogn) время. Идея состоит в том, чтобы найти минимальное значение в данном массиве. Как только у нас будет индекс минимального значения, максимальная площадь будет максимальной из следующих трех значений.
а) Максимальная площадь в левой части минимального значения (не включая минимальное значение)
б) Максимальная площадь в правой части минимального значения (не включая минимальное значение)
в) Количество баров, умноженное на минимальное значение.
Площади слева и справа от минимального значения могут быть вычислены рекурсивно. Если мы используем линейный поиск, чтобы найти минимальное значение, то временная сложность этого алгоритма в наихудшем случае становится O (n ^ 2). В худшем случае у нас всегда есть (n-1) элементов на одной стороне и 0 элементов на другой стороне, и если минимум поиска занимает O (n) времени, мы получаем повторение, подобное наихудшему случаю быстрой сортировки.
Как найти минимум эффективно? Для этого можно использовать минимальный диапазон запросов с использованием дерева сегментов . Построим дерево сегментов с заданной высотой гистограммы. После построения дерева сегментов все запросы с минимальным диапазоном занимают время O (Logn) . Так во всей сложности алгоритм становится.

Общее время = время построения дерева сегментов + время рекурсивного поиска максимальной площади

Время построения дерева сегментов O (n) . Пусть время, чтобы рекурсивно найти максимальную площадь, будет T (n). Это можно записать следующим образом.
T (n) = O (Logn) + T (n-1)
Решением вышеупомянутого рецидива является O (nLogn). Таким образом, общее время равно O (n) + O (nLogn), что равно O (nLogn).

Следующее — реализация C ++ вышеупомянутого алгоритма.

// Программа «Разделяй и властвуй», чтобы найти максимальную прямоугольную область в гистограмме
#include <math.h>
#include <limits.h>
#include <iostream>

using namespace std;

  
// Полезная функция для поиска минимум трех целых

int max(int x, int y, int z)

return max(max(x, y), z); }

  
// Полезная функция для получения минимум двух чисел в исторических []

int minVal(int *hist, int i, int j)

{

    if (i == -1) return j;

    if (j == -1) return i;

    return (hist[i] < hist[j])? i : j;

}

  
// Полезная функция для получения среднего индекса из угловых индексов.

int getMid(int s, int e)

{   return s + (e -s)/2; }

  
/ * Рекурсивная функция для получения индекса минимального значения в заданном диапазоне

    индексов. Ниже приведены параметры для этой функции.

  

    hist -> Входной массив, для которого построено дерево сегментов

    st -> Указатель на дерево сегментов

    index -> Индекс текущего узла в дереве сегментов. Изначально 0

             передается от имени root всегда с индексом 0

    ss & se -> Начальный и конечный индексы сегмента, представленного

                 текущий узел, т. е. st [index]

    qs & qe -> начальные и конечные индексы диапазона запросов * /

int RMQUtil(int *hist, int *st, int ss, int se, int qs, int qe, int index)

{

    // Если сегмент этого узла является частью заданного диапазона, возвращаем

    // мин отрезка

    if (qs <= ss && qe >= se)

        return st[index];

  

    // Если сегмент этого узла находится за пределами указанного диапазона

    if (se < qs || ss > qe)

        return -1;

  

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

    int mid = getMid(ss, se);

    return minVal(hist, RMQUtil(hist, st, ss, mid, qs, qe, 2*index+1),

                  RMQUtil(hist, st, mid+1, se, qs, qe, 2*index+2));

}

  
// Возвращаем индекс минимального элемента в диапазоне от индекса qs (quey start) до
// qe (конец запроса). В основном использует RMQUtil ()

int RMQ(int *hist, int *st, int n, int qs, int qe)

{

    // Проверяем ошибочные входные значения

    if (qs < 0 || qe > n-1 || qs > qe)

    {

        cout << "Invalid Input";

        return -1;

    }

  

    return RMQUtil(hist, st, 0, n-1, qs, qe, 0);

}

  
// Рекурсивная функция, которая создает дерево сегментов для исторических [ss..se].
// si - индекс текущего узла в сегментном дереве st

int constructSTUtil(int hist[], int ss, int se, int *st, int si)

{

    // Если в массиве есть один элемент, сохраняем его в текущем узле

    // сегментируем дерево и возвращаем

    if (ss == se)

       return (st[si] = ss);

  

    // Если есть более одного элемента, то повторить для левого и

    // правильные поддеревья и храним минимум двух значений в этом узле

    int mid = getMid(ss, se);

    st[si] =  minVal(hist, constructSTUtil(hist, ss, mid, st, si*2+1),

                     constructSTUtil(hist, mid+1, se, st, si*2+2));

    return st[si];

}

  
/ * Функция для построения дерева сегментов из заданного массива. Эта функция

   выделяет память для дерева сегментов и вызывает constructSTUtil () для

   заполнить выделенную память * /

int *constructST(int hist[], int n)

{

    // Выделить память для дерева сегментов

    int x = (int)(ceil(log2(n))); // Высота сегмента дерева

    int max_size = 2*(int)pow(2, x) - 1; // Максимальный размер дерева сегментов

    int *st = new int[max_size];

  

    // Заполняем выделенную память st

    constructSTUtil(hist, 0, n-1, st, 0);

  

    // Возвращаем построенное дерево сегментов

    return st;

}

  
// Рекурсивная функция для поиска максимальной прямоугольной области.
// Использует дерево сегментов 'st', чтобы найти минимальное значение в исторических [l..r]

int getMaxAreaRec(int *hist, int *st, int n, int l, int r)

{

    // Базовые случаи

    if (l > r)  return INT_MIN;

    if (l == r)  return hist[l];

  

    // Находим индекс минимального значения в заданном диапазоне

    // Это занимает O (Logn) время

    int m = RMQ(hist, st, n, l, r);

  

    / * Вернуть максимум из следующих трех возможных случаев

       а) Максимальная площадь слева от минимального значения (не включая минимальное значение)

       а) Максимальная площадь справа от минимального значения (не включая минимальное значение)

       в) Максимальная площадь, включая мин * /

    return max(getMaxAreaRec(hist, st, n, l, m-1),

               getMaxAreaRec(hist, st, n, m+1, r),

               (r-l+1)*(hist[m]) );

}

  
// Основная функция для поиска максимальной площади

int getMaxArea(int hist[], int n)

{

    // Построить дерево сегментов из заданного массива. Это занимает

    // Вовремя

    int *st = constructST(hist, n);

  

    // Используем рекурсивную функцию полезности, чтобы найти

    // максимальная площадь

    return getMaxAreaRec(hist, st, n, 0, n-1);

}

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

int main()

{

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

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

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

    return 0;

}

Выход:

Maximum area is 12

Эта проблема может быть решена за линейное время. См. Ниже набор 2 для линейного решения времени.
Линейное временное решение для самой большой прямоугольной области в гистограмме

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

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

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

0.00 (0%) 0 votes