AC Python code


  • 0
    H

    The first solution, search each height while finding the width.

    class Solution(object):
        def largestRectangleArea(self, heights):
            """
            :type heights: List[int]
            :rtype: int
            """
            n = len(heights)
            if n == 0:  return 0
            max_rec = -1
            left, right = [i for i in range(n)], [i for i in range(n)]    # left[i] is the most left 'index' making height[index]>=height[i]
            # fill the list left (make use of previous results)
            for i in range(n):
                p = i
                while p>=0 and heights[p]>=heights[i]:   
                    if p != left[p]:    p = left[p]
                    else:   p -= 1
                left[i] = p + 1
            # fill the list right
            for j in range(n-1, -1, -1):
                p = j
                while p<n and heights[p]>=heights[j]:
                    if p != right[p]:   p = right[p]
                    else:   p += 1
                right[j] = p - 1
            # scan heights and calculate max rectangle containing each elements
            for k in range(n):
                max_rec = max(heights[k]*(right[k]-left[k]+1), max_rec)
            print(left, right)
            return max_rec
                        
    

    The second solution, using stack (insert a dummy 0 to the head of heights and push 0 index to stack).

    class Solution(object):
        def largestRectangleArea(self, heights):
            """
            :type heights: List[int]
            :rtype: int
            """
            n = len(heights)
            height, stack, h, max_area = [0]+heights, [0], 0, 0
            for i in range(1, n+1):
                while height[i] < height[stack[-1]]:
                    h = height[stack[-1]]
                    stack.pop()
                    w = i - stack[-1] - 1
                    max_area = max(w*h, max_area)
                stack.append(i)
            # in case stack is still not empty
            r = stack[-1] + 1
            while len(stack)>1:
                h = height[stack[-1]]
                stack.pop()
                w = r - stack[-1] - 1 
                max_area = max(w*h, max_area)
                
            return max_area
    

    Avoid treating not-empty stack by inserting another dummy 0 to the tail of heights.

    class Solution(object):
        def largestRectangleArea(self, heights):
            """
            :type heights: List[int]
            :rtype: int
            """
            n = len(heights)
            height, stack, h, max_area = [0]+heights+[0], [0], 0, 0
            for i in range(1, n+2):
                while height[i] < height[stack[-1]]:
                    h = height[stack[-1]]
                    stack.pop()
                    w = i - stack[-1] - 1
                    max_area = max(w*h, max_area)
                stack.append(i)
                
            return max_area
    

Log in to reply
 

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