Largest Rectangle In Histogram
Hard
Python
Loops
21 views
Problem Statement
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.
Example
1 7 2 1 5 6 2 3 1
10
Constraints
Sum of n over all testcases
Input / Output Format
Input Format
First integer t. For each: n then n heights.
Output Format
t lines max areas.
Constraints
Sum of n over all testcases
Examples
Input:
1
7
2 1 5 6 2 3 1
Output:
10
Example Solution (Public)
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))
Official Solution Code
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))
Please login to submit solutions.