Task 79. Гистограмма
UniLecsЗадача: дана гистограмма, она представлена числовым массивом:
[2, 1, 4, 5, 1, 3, 3]
Массив задает высоты прямоугольников, из ктр сформирована гистограмма, ширина этих прямоугольников равна 1 единице.
Необходимо определить площадь самого большого прямоугольника в гистограмме, этот прямоугольник должен быть на общей базовой линии.
Входные данные: arr - массив, ктр задает высоты прямоугольников гистограммы слева направо.
Вывод: S - площадь самого большого прямоугольника в гистограмме, этот прямоугольник должен быть на общей базовой линии.
Пример:
arr = [2, 1, 4, 5, 1, 3, 3]
Smax = 8
Идея: есть несколько подходов к решению этой задачи, мы воспользуемся не самым рациональным, но довольно простым и понятным решением. Рассмотрим его подробнее.
Для каждого i-го прямоугольника постараемся раздвинуть его границы влево и вправо пока это возможно (т.е. высоты всех прямоугольников от left до right не менее hi, 1 <= left <= i <= right). В итоге мы получим максимально возможный прямоугольник, вписанный в гистограмму, который упирается в верх i-го прямоугольника. Далее среди всех таких прямоугольников ищем максимальный.
Реализация:
https://gist.github.com/unilecs/d64e861ca49c3fc335483b38dc1020b0
Тест: