PrepBro
← Назад к вопросам

Наибольший прямоугольник в гистограмме

1.2 Junior🔥 151 комментариев
#Python Core

Условие

Дан массив высот столбцов гистограммы (ширина каждого столбца = 1). Найдите площадь наибольшего прямоугольника, который можно вписать в гистограмму.

Пример

largest_rectangle([2, 1, 5, 6, 2, 3]) → 10

Объяснение: прямоугольник с высотой 5 и шириной 2 (столбцы 5 и 6)

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Наибольший прямоугольник в гистограмме

Задача

Дан массив высот столбцов гистограммы (ширина каждого столбца = 1). Требуется найти максимальную площадь прямоугольника, который можно вписать в гистограмму.

Для примера largest_rectangle([2, 1, 5, 6, 2, 3]):

  • Прямоугольник с высотой 5 и шириной 2 (столбцы с индексами 2 и 3) имеет площадь 5 × 2 = 10
  • Это максимальная площадь

Решение 1: Stack (Оптимальное, O(n))

Используем монотонный стек для отслеживания высот в возрастающем порядке.

Ключевая идея:

  • Когда встречаем высоту меньше вершины стека, начинаем вычислять площади
  • Для каждой высоты h, ширина прямоугольника определяется расстоянием до предыдущей более низкой высоты
def largest_rectangle(heights):
    """
    Находит наибольший прямоугольник в гистограмме за O(n).
    
    Идея:
    - Стек хранит индексы высот в возрастающем порядке
    - Когда встречаем меньшую высоту, начинаем вычислять площади
    - Для каждой высоты определяем максимальную ширину
    """
    if not heights:
        return 0
    
    stack = []  # Хранит индексы
    max_area = 0
    
    for i in range(len(heights)):
        # Пока текущая высота меньше высоты на вершине стека
        while stack and heights[stack[-1]] > heights[i]:
            # Вычисляем площадь с высотой stack.pop()
            h_index = stack.pop()
            h = heights[h_index]
            
            # Определяем ширину
            # Справа: i (текущий индекс)
            # Слева: stack[-1] если есть, иначе -1
            width = i if not stack else i - stack[-1] - 1
            
            area = h * width
            max_area = max(max_area, area)
        
        stack.append(i)
    
    # Обработаем оставшиеся элементы в стеке
    while stack:
        h_index = stack.pop()
        h = heights[h_index]
        
        width = len(heights) if not stack else len(heights) - stack[-1] - 1
        area = h * width
        max_area = max(max_area, area)
    
    return max_area

# Тестирование
print(largest_rectangle([2, 1, 5, 6, 2, 3]))  # 10
print(largest_rectangle([2, 4]))  # 4
print(largest_rectangle([2, 1, 2]))  # 2
print(largest_rectangle([0, 9]))  # 9

Сложность:

  • Временная: O(n) — каждый элемент добавляется и удаляется один раз
  • Пространственная: O(n) — размер стека в худшем случае

Пошаговое объяснение

Для heights = [2, 1, 5, 6, 2, 3]:

i=0: heights[0]=2
  stack = [0]

i=1: heights[1]=1
  heights[1]=1 < heights[0]=2
  Вычисляем: h=2, width=1 (от начала до текущего), area=2×1=2
  stack = [1]

i=2: heights[2]=5
  heights[2]=5 > heights[1]=1
  stack = [1, 2]

i=3: heights[3]=6
  heights[3]=6 > heights[2]=5
  stack = [1, 2, 3]

i=4: heights[4]=2
  heights[4]=2 < heights[3]=6
  Вычисляем h=6: width=1 (от 2 до 4), area=6×1=6
  Вычисляем h=5: width=2 (от 1 до 4), area=5×2=10 ← МАКСИМУМ
  heights[4]=2 == heights[1]=1
  stack = [1, 4]

i=5: heights[5]=3
  heights[5]=3 > heights[4]=2
  stack = [1, 4, 5]

Обработка оставшихся:
  h=3: width=1, area=3×1=3
  h=2: width=4 (от начала 0 до конца 6), area=2×4=8
  h=1: width=6, area=1×6=6

Максимум: 10 ✓

Решение 2: Divide & Conquer (O(n log n))

Рекурсивно делим гистограмму по минимальной высоте.

def largest_rectangle_divide(heights):
    """
    Используется разделение и покорение.
    Сложность: O(n log n) в среднем, O(n²) в худшем.
    """
    def helper(left, right):
        if left > right:
            return 0
        
        # Находим минимальную высоту
        min_index = left
        for i in range(left, right + 1):
            if heights[i] < heights[min_index]:
                min_index = i
        
        # Площадь прямоугольника с минимальной высотой
        area = heights[min_index] * (right - left + 1)
        
        # Рекурсивно вычисляем для левой и правой частей
        area = max(area, helper(left, min_index - 1))
        area = max(area, helper(min_index + 1, right))
        
        return area
    
    return helper(0, len(heights) - 1)

print(largest_rectangle_divide([2, 1, 5, 6, 2, 3]))  # 10

Сложность: O(n log n) в среднем, O(n²) в худшем

Решение 3: Брутфорс (O(n²))

Для каждого индекса находим максимальную ширину.

def largest_rectangle_brute(heights):
    """
    Простой подход: для каждой высоты найти максимальную ширину.
    Сложность: O(n²)
    """
    if not heights:
        return 0
    
    max_area = 0
    
    for i in range(len(heights)):
        # Ищем влево
        left = i
        while left > 0 and heights[left - 1] >= heights[i]:
            left -= 1
        
        # Ищем вправо
        right = i
        while right < len(heights) - 1 and heights[right + 1] >= heights[i]:
            right += 1
        
        # Вычисляем площадь
        width = right - left + 1
        area = heights[i] * width
        max_area = max(max_area, area)
    
    return max_area

print(largest_rectangle_brute([2, 1, 5, 6, 2, 3]))  # 10

Сложность: O(n²) — медленно

Решение 4: Оптимизированный Брутфорс (O(n²) с лучшей константой)

def largest_rectangle_optimized(heights):
    """
    Брутфорс с предварительно вычисленными границами.
    Сложность: O(n²), но с меньшей константой.
    """
    if not heights:
        return 0
    
    n = len(heights)
    left = [0] * n
    right = [0] * n
    
    # Вычисляем для каждого элемента индекс первого меньшего слева
    left[0] = -1
    for i in range(1, n):
        j = i - 1
        while j >= 0 and heights[j] >= heights[i]:
            j = left[j]
        left[i] = j
    
    # Вычисляем для каждого элемента индекс первого меньшего справа
    right[n - 1] = n
    for i in range(n - 2, -1, -1):
        j = i + 1
        while j < n and heights[j] >= heights[i]:
            j = right[j]
        right[i] = j
    
    # Вычисляем максимальную площадь
    max_area = 0
    for i in range(n):
        width = right[i] - left[i] - 1
        area = heights[i] * width
        max_area = max(max_area, area)
    
    return max_area

print(largest_rectangle_optimized([2, 1, 5, 6, 2, 3]))  # 10

Сравнение подходов

МетодВременнаяПространственнаяОписание
StackO(n)O(n)Оптимальное, используй это
Divide & ConquerO(n log n)O(log n)Хорошо в среднем
Оптимизированный BFO(n²)O(n)Работает быстрее обычного
Простой BFO(n²)O(n)Просто, но медленно

Обобщение: Maximal Rectangle

Этот алгоритм базис для более сложной задачи — максимальный прямоугольник в матрице:

def maximal_rectangle(matrix):
    """
    Находит максимальный прямоугольник в матрице.
    Идея: для каждой строки вычисляем высоты и применяем largest_rectangle.
    """
    if not matrix:
        return 0
    
    rows = len(matrix)
    cols = len(matrix[0])
    heights = [0] * cols
    max_area = 0
    
    for row in range(rows):
        # Обновляем высоты
        for col in range(cols):
            heights[col] = heights[col] + 1 if matrix[row][col] == 1 else 0
        
        # Применяем алгоритм гистограммы
        max_area = max(max_area, largest_rectangle(heights))
    
    return max_area

Ключевые моменты

  1. Монотонный стек — основная техника
  2. Ширина прямоугольника = расстояние между индексами меньших элементов
  3. O(n) сложность достигается благодаря тому, что каждый элемент обрабатывается дважды
  4. Применимо к другим задачам со стеком (валидные скобки, нарастающий подмассив)

Заключение

Stack метод — классическое решение для задачи наибольшего прямоугольника в гистограмме. Это O(n) алгоритм, который часто встречается на интервью у компаний наподобие Google, Facebook, Amazon. Ключевой навык — понимание монотонного стека.

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