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

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

# Example: heights = [2, 1, 5, 6, 2, 3]
# Rectangles:
# width=1, height=6 at index 3 => area=6
# width=2, height=5 at indices 2-3 => area=10 (maximum!)
# width=6, height=1 across all => area=6
# width=3, height=2 at indices 2-4 => area=6
heights = [2, 1, 5, 6, 2, 3]
print('Heights:', heights)
print('Expected max area: 10 (bars of height 5 and 6, width 2)')

# Brute force for small inputs:
def brute_force(heights):
    n = len(heights)
    max_area = 0
    for i in range(n):
        min_h = heights[i]
        for j in range(i, n):
            min_h = min(min_h, heights[j])
            max_area = max(max_area, min_h * (j - i + 1))
    return max_area

print('Brute force answer:', brute_force(heights))  # 10

Главная идея: что ограничивает прямоугольник каждого столбца?

heights = [2, 1, 5, 6, 2, 3]
n = len(heights)

# Find PSE and NSE for each bar
pse = [-1] * n   # index of previous smaller element
nse = [n] * n    # index of next smaller element (default: beyond array)

# PSE
stack = []
for i in range(n):
    while stack and heights[stack[-1]] >= heights[i]:
        stack.pop()
    pse[i] = stack[-1] if stack else -1
    stack.append(i)

# NSE
stack = []
for i in range(n - 1, -1, -1):
    while stack and heights[stack[-1]] >= heights[i]:
        stack.pop()
    nse[i] = stack[-1] if stack else n
    stack.append(i)

max_area = 0
for i in range(n):
    width = nse[i] - pse[i] - 1
    area = heights[i] * width
    print(f'Bar {i} (h={heights[i]}): PSE={pse[i]}, NSE={nse[i]}, width={width}, area={area}')
    max_area = max(max_area, area)
print('Max area:', max_area)

Однопроходное решение с монотонным стеком

def largest_rectangle(heights):
    stack = []   # monotonic increasing: indices of bars
    max_area = 0
    heights = heights + [0]  # sentinel: forces all bars to be popped

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]       # height of the rectangle
            width = i if not stack else i - stack[-1] - 1  # left boundary
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

print(largest_rectangle([2, 1, 5, 6, 2, 3]))  # 10
print(largest_rectangle([2, 4]))               # 4
print(largest_rectangle([1, 1]))               # 2
print(largest_rectangle([0, 9]))               # 9
print(largest_rectangle([6, 7, 5, 2, 4, 5, 9, 3]))  # 16

Трассировка однопроходного алгоритма

def largest_rectangle_trace(heights):
    stack = []
    max_area = 0
    hs = heights + [0]

    for i, h in enumerate(hs):
        while stack and hs[stack[-1]] > h:
            top = stack.pop()
            w = i if not stack else i - stack[-1] - 1
            area = hs[top] * w
            print(f'  Pop bar {top} (h={hs[top]}): width={w}, area={area}', end='')
            if area > max_area:
                max_area = area
                print(' *** NEW MAX ***', end='')
            print()
        print(f'i={i} h={h}: push {i}, stack={[hs[s] for s in stack + [i]]}')
        stack.append(i)
    print(f'Max area: {max_area}')
    return max_area

largest_rectangle_trace([2, 1, 5, 6, 2, 3])

Вычисление ширины: почему i - stack[-1] - 1?

# Illustrating left/right boundary logic
heights = [1, 3, 5, 2]
# After processing with stack:
# When we pop bar 2 (h=5) at i=3 (h=2):
#   stack after pop = [0, 1]   => left boundary = 1+1=2, right=3-1=2 => width=1
# When we pop bar 1 (h=3) at i=3 (h=2):
#   stack after pop = [0]       => left boundary = 0+1=1, right=3-1=2 => width=2
# etc.

def compute_boundaries(heights):
    hs = heights + [0]
    stack = []
    for i, h in enumerate(hs):
        while stack and hs[stack[-1]] > h:
            top = stack.pop()
            if stack:
                left = stack[-1] + 1
                width = i - stack[-1] - 1
            else:
                left = 0
                width = i
            print(f'Bar {top} (h={hs[top]}): extends from {left} to {i-1}, width={width}')
        stack.append(i)

compute_boundaries([2, 1, 5, 6, 2, 3])

Максимальный прямоугольник в двоичной матрице

def maximal_rectangle(matrix):
    if not matrix or not matrix[0]:
        return 0
    n = len(matrix[0])
    heights = [0] * n
    max_area = 0

    def hist_max_area(h):
        stack, area = [], 0
        for i, hh in enumerate(h + [0]):
            while stack and h[stack[-1]] > hh:
                top = stack.pop()
                w = i if not stack else i - stack[-1] - 1
                area = max(area, h[top] * w)
            stack.append(i)
        return area

    for row in matrix:
        for j in range(n):
            heights[j] = heights[j] + 1 if row[j] == '1' else 0
        max_area = max(max_area, hist_max_area(heights[:]))
    return max_area

matrix = [['1','0','1','0','0'],
          ['1','0','1','1','1'],
          ['1','1','1','1','1'],
          ['1','0','0','1','0']]
print(maximal_rectangle(matrix))  # 6

Граничные случаи в задачах о гистограммах

def largest_rectangle(heights):
    stack = []
    max_area = 0
    heights = heights + [0]
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            top = stack.pop()
            w = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, heights[top] * w)
        stack.append(i)
    return max_area

# Edge cases
print(largest_rectangle([5, 5, 5, 5]))    # 20 (all same)
print(largest_rectangle([1, 2, 3, 4, 5])) # 9 (increasing: 3*3)
print(largest_rectangle([5, 4, 3, 2, 1])) # 9 (decreasing: 3*3)
print(largest_rectangle([5]))              # 5 (single bar)
print(largest_rectangle([0, 0, 0]))        # 0 (all zero)
print(largest_rectangle([3, 0, 3]))        # 3 (zero splits)

Альтернатива: разделяй и властвуй

def largest_rectangle_dc(heights, lo=0, hi=None):
    if hi is None:
        hi = len(heights) - 1
    if lo > hi:
        return 0
    # Find the index of the minimum height in [lo, hi]
    min_idx = lo
    for i in range(lo, hi + 1):
        if heights[i] < heights[min_idx]:
            min_idx = i
    # Three options:
    # 1. Max rect entirely in left half
    # 2. Max rect entirely in right half
    # 3. Max rect spanning entire [lo, hi] with height = min
    full_width_area = heights[min_idx] * (hi - lo + 1)
    left_area  = largest_rectangle_dc(heights, lo, min_idx - 1)
    right_area = largest_rectangle_dc(heights, min_idx + 1, hi)
    return max(full_width_area, left_area, right_area)

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

Шаблон гистограммы: количество подмассивов

def sum_of_subarray_minimums(arr):
    n = len(arr)
    pse = [-1] * n   # previous strictly smaller element
    nse = [n] * n    # next smaller or equal element

    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        pse[i] = stack[-1] if stack else -1
        stack.append(i)

    stack = []
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        nse[i] = stack[-1] if stack else n
        stack.append(i)

    MOD = 10**9 + 7
    total = 0
    for i in range(n):
        left_count = i - pse[i]          # subarrays where i is leftmost min
        right_count = nse[i] - i        # subarrays where i is the min
        total += arr[i] * left_count * right_count
    return total % MOD

print(sum_of_subarray_minimums([3, 1, 2, 4]))  # 17
print(sum_of_subarray_minimums([11, 81, 94, 43, 3]))  # 444

Практические советы для собеседования

# Final clean solution for interview
def largest_rectangle_in_histogram(heights):
    stack = []
    max_area = 0
    for i, h in enumerate(heights + [0]):  # sentinel forces final pops
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

# Verify all test cases from earlier
test_cases = [
    ([2, 1, 5, 6, 2, 3], 10),
    ([6, 7, 5, 2, 4, 5, 9, 3], 16),
    ([1], 1),
    ([2, 0, 2], 2),
    ([], 0),
]
for heights, expected in test_cases:
    if not heights:
        result = 0
    else:
        result = largest_rectangle_in_histogram(heights)
    status = 'PASS' if result == expected else 'FAIL'
    print(f'{status}: {heights} => {result} (expected {expected})')

Сумма диапазонов подмассивов и похожие варианты

def sum_subarray_ranges(nums):
    n = len(nums)
    # Sum of subarray max - sum of subarray min
    def contrib(arr, is_max):
        # Count contribution of each element as max (or min)
        n = len(arr)
        left = [0]*n; right = [0]*n
        stack = []
        for i in range(n):
            while stack and (arr[stack[-1]] < arr[i] if is_max else arr[stack[-1]] > arr[i]):
                stack.pop()
            left[i] = i - (stack[-1] if stack else -1)
            stack.append(i)
        stack = []
        for i in range(n-1, -1, -1):
            while stack and (arr[stack[-1]] <= arr[i] if is_max else arr[stack[-1]] >= arr[i]):
                stack.pop()
            right[i] = (stack[-1] if stack else n) - i
            stack.append(i)
        return sum(arr[i] * left[i] * right[i] for i in range(n))
    return contrib(nums, True) - contrib(nums, False)

print(sum_subarray_ranges([1, 2, 3]))    # 4
print(sum_subarray_ranges([1, 3, 3]))    # 4
print(sum_subarray_ranges([4, -2, -3, 4, 1]))  # 59

Быстрая проверка

Итоги урока