histogram1.py - master - k2709/matrix_task

histogram1.py
81 строка3 KB
urik
Initial commit
06 янв 2025, 18:02
06 янв 2025, 18:029d2fadf
'''

# Нахождение площади наибольшего прямоугольника в гистограмме

## Условие

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

**Входные данные:** массив целых чисел `heights`,
где 1 <= len(heights) <= $10^4$ и 0 <= heights[i] <= $10^4$  .

**Выходные данные:** целое число - площадь наибольшего
прямоугольника в гистограмме.

## Примеры

**Пример 1:**

**Вход:** heights = [2,1,5,6,2,3]

**Выход:** 10

**Пояснение:** В этом примере наибольший прямоугольник, который можно
получить в гистограмме имеет высоту 5 и ширину 2,
что дает площадь равную 10.

**Пример 2:**

**Вход:** heights = [2,4]

**Выход:** 4

## Решение

Для решения данной задачи будем использовать алгоритм "стек".
Данный алгоритм позволяет находить площадь наибольшего
прямоугольника в гистограмме за линейное время.

### Шаги алгоритма

1. Создаем пустой стек `stack` для хранения индексов столбцов.
2. Проходим по массиву `heights` от начала до конца.
3. Если стек пустой или текущий элемент `heights[i]` больше или
равен элементу `heights[stack[-1]]`, то добавляем индекс
текущего элемента в стек `stack`.
4. Если текущий элемент `heights[i]` меньше элемента `heights[stack[-1]]`,
то извлекаем из стека последний элемент `j`. Высота прямоугольника
равна `heights[j]`, а ширина равна `i - stack[-1] - 1`. Таким образом,
площадь прямоугольника равна `heights[j] * (i - stack[-1] - 1)`.
Если стек пустой, то ширина равна `i`.
5. Если текущая площадь больше максимальной площади, то обновляем
максимальную площадь.
6. Повторяем шаги 3-5 пока не пройдем весь массив.

### Пример
Пусть дана гистограмма с высотами столбцов [2,1,5,6,2,3].
Максимальная площадь равна 10.
'''

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    i = 0
    while i < len(heights):
        if not stack or heights[i] >= heights[stack[-1]]:
            stack.append(i)
            i += 1
        else:
            j = stack.pop()
            area = heights[j] * ((i - stack[-1] - 1) if stack else i)
            max_area = max(max_area, area)
    while stack:
        j = stack.pop()
        area = heights[j] * ((i - stack[-1] - 1) if stack else i)
        max_area = max(max_area, area)
    return max_area

heigths = [2,1,5,6,2,3,2,2,2,2]
print(largest_rectangle_area(heigths))