My 8-line python solution with explanation


  • 0
    D

    8 lines, beats 92%

    class Solution(object):
        def largestRectangleArea(self, heights):
            """
            :type heights: List[int]
            :rtype: int
            """
            s, res, heights = [], 0, [0] + heights + [0] # add the first 0 to let s[-1] be always avaliable, add the last 0 to calculate when meeting the end
            for i, height in enumerate(heights):
                if len(s) > 0:
                    while height < heights[s[-1]]:
                        top = s.pop()
                        res = max(res, heights[top] * (i - s[-1] - 1))  # The stack have such feature: all items between s[-1] and i (both not including) are heighter than s[top]. If items after "top" are lower than heights[top], heights[top] will be poped; the items between s[-1] (not including) and top are obviously taller than heights[top] (because heights[s[-1]] is the heightest between all items lower than heights[top], so all items between s[-1] and i (both not including) are heighter than s[top]
                s.append(i)
            return res
    

Log in to reply
 

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