Гистограмма является многоугольником, сформированным из последовательности прямоугольников, выровненных на общей базовой линии. Прямоугольники имеют равную ширину, но могут иметь различные высоты. Например, фигура слева показывает гистограмму, которая состоит из прямоугольников с высотами 2, 1, 4, 5, 1, 3, 3. Все прямоугольники на этом рисунке имеют ширину, равную 1.
Обычно гистограммы используются для представления дискретных распределений, например, частоты символов в текстах. Отметьте, что порядок прямоугольников очень важен. Вычислите область самого большого прямоугольника в гистограмме, который также находится на общей базовой линии. На рисунке справа заштрихованная фигура является самым большим выровненным прямоугольником на изображенной гистограмме.
В первой строке записано число n (0 ≤ n ≤ 106
) - количество прямоугольников гистограммы. Затем следует n целых чисел h1
, ..., hn
(0 ≤ hi
≤ 109
). Эти числа обозначают высоты прямоугольников гистограммы слева направо. Ширина каждого прямоугольника равна 1.
Вывести площадь самого большого прямоугольника в гистограмме. Помните, что этот прямоугольник должен быть на общей базовой линии.
#include <iostream>
#include <stack>
using namespace std;
struct Node
{
int x, Height;
Node(int x, int Height) : x(x), Height(Height) {};
};
stack<Node> s;
int main() {
int h, n, i;
long res;
scanf("%d", &n);
s.push(Node(0, 0));
for (res = 0, i = 1; i <= n + 1; i++)
{
if (i <= n) scanf("%d", &h);
else h = 0;
int x = i;
while (h < s.top().Height)
{
x = s.top().x;
int Height = s.top().Height;
s.pop();
long area = 1L * Height * (i - x);
if (area > res) res = area;
}
if (h > s.top().Height) s.push(Node(x, h));
}
printf("%ld\n", res);
return 0;
}
Есть решение которого нет на сайте? Пиши admin@devexe.top