39 lines
1.0 KiB
Python
39 lines
1.0 KiB
Python
"""Largest Rectangle in Histogram.
|
|
|
|
Given bar heights, find area of largest rectangle using contiguous bars.
|
|
O(n) via monotonic increasing stack of indices with a sentinel 0.
|
|
Brute-force oracle included for verification.
|
|
"""
|
|
from typing import List
|
|
|
|
|
|
def largest_rectangle_area(heights: List[int]) -> int:
|
|
if not heights:
|
|
return 0
|
|
stack: List[int] = []
|
|
best = 0
|
|
h = list(heights) + [0]
|
|
for i, height in enumerate(h):
|
|
while stack and h[stack[-1]] > height:
|
|
idx = stack.pop()
|
|
left = stack[-1] if stack else -1
|
|
width = i - left - 1
|
|
area = h[idx] * width
|
|
if area > best:
|
|
best = area
|
|
stack.append(i)
|
|
return best
|
|
|
|
|
|
def _brute(heights: List[int]) -> int:
|
|
n = len(heights)
|
|
best = 0
|
|
for i in range(n):
|
|
mn = heights[i]
|
|
for j in range(i, n):
|
|
mn = min(mn, heights[j])
|
|
area = mn * (j - i + 1)
|
|
if area > best:
|
|
best = area
|
|
return best
|