2024-09-03 18:19

Status: child

Tags: Leetcode leetcode leetcode-hard stack

Largest Rectangle in Histogram

Code

class Solution(object):
 
	def largestRectangleArea(self, heights):	
		"""		
		:type heights: List[int]		
		:rtype: int		
		"""
 
		maxArea = 0		
		stack = [] # pair: (index, height)
		
		for i, h in enumerate(heights):		
			start = i			
			while stack and stack[-1][1] > h:			
				index, height = stack.pop()				
				maxArea = max(maxArea, height * (i - index))				
				start = index				
				stack.append((start, h))
		
		for i, h in stack:		
			maxArea = max(maxArea, h * (len(heights) - i))
		
		return maxArea

References

Neetcode