Python O(n) time and space solution, 55ms beat 99%


  • 0
    S
    def _max_histogram_rectangle(heights):
        stack = []
        area = 0
        for i, h in enumerate(heights):
            if not stack or h > stack[-1][1]:
                stack.append((i, h))
            elif stack[-1][1] == h:
                continue
            else:
                while stack and stack[-1][1] > h:
                    left, height = stack.pop()
                    area = max(area, height*(i-left))
                stack.append((left, h))
        
        while stack:
            left, height = stack.pop()
            area = max(area, (len(heights) - left)*height)
        
        return area
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.