Python solution without using stack. (with explanation)

  • 4

    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.