Largest Rectangle In Histogram
Python
Hard
5 views
Problem Description
For each testcase you get n bar heights. Compute largest rectangle area in histogram.
Input Format
First integer t. For each: n then n heights.
Output Format
t lines max areas.
Constraints
Sum of n over all testcases
Official Solution
import sys
p=sys.stdin.read().strip().split()
if not p:
sys.exit(0)
it=iter(p)
t=int(next(it))
out=[]
for _ in range(t):
n=int(next(it))
h=[int(next(it)) for _ in range(n)]
st=[]
best=0
for i in range(n+1):
cur=0 if i==n else h[i]
while st and (cur<h[st[-1]]):
top=st.pop()
height=h[top]
left=st[-1]+1 if st else 0
width=i-left
area=height*width
if area>best:
best=area
st.append(i)
if i==n:
st.pop()
out.append(str(best))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!