Python solution without using stack. (with explanation)


  • 4
    S

    The algorithm using stack actually is not quite intuitive. At least I won't think about using it at first time.

    It is more natural to think about this way. Let left[i] to indicate how many bars to the left (including the bar at index i) are equal or higher than bar[i], right[i] is that to the right of bar[i], so the the square of the max rectangle containing bar[i] is simply height[i] * (left[i] + right[i] - 1)

    class Solution:
        # @param height, a list of integer
        # @return an integer
        def largestRectangleArea(self, height):
            n = len(height)
    
            # left[i], right[i] represent how many bars are >= than the current bar
    
            left = [1] * n
            right = [1] * n
            max_rect = 0
    
            # calculate left
            for i in range(0, n):
                j = i - 1
                while j >= 0:
                    if height[j] >= height[i]:
                        left[i] += left[j]
                        j -= left[j]
                    else: break
    
            # calculate right
            for i in range(n - 1, -1, -1):
                j = i + 1
                while j < n:
                    if height[j] >= height[i]:
                        right[i] += right[j]
                        j += right[j]
                    else: break
    
            for i in range(0, n):
                max_rect = max(max_rect, height[i] * (left[i] + right[i] - 1))
    
            return max_rect
    

    Note, this algorithm runs O(n) not O(n^2)! The while loop in the for loop jumps forward or backward by the steps already calculated.


  • 0

    This is definitely a more intuitive way than the stack. Especially the jump forward idea!


Log in to reply
 

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