Python solution without using stack. (with explanation)
The algorithm using stack actually is not quite intuitive. At least I won't think about using it at first time.\n\nIt is more natural to think about this way. L
The algorithm using stack actually is not quite intuitive. At least I won't think about using it at first time.\n\nIt 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)\n\n    class Solution:\n        # @param height, a list of integer\n        # @return an integer\n        def largestRectangleArea(self, height):\n            n = len(height)\n\n            # left[i], right[i] represent how many bars are >= than the current bar\n\n            left = [1] * n\n            right = [1] * n\n            max_rect = 0\n\n            # calculate left\n            for i in range(0, n):\n                j = i - 1\n                while j >= 0:\n                    if height[j] >= height[i]:\n                        left[i] += left[j]\n                        j -= left[j]\n                    else: break\n\n            # calculate right\n            for i in range(n - 1, -1, -1):\n                j = i + 1\n                while j < n:\n                    if height[j] >= height[i]:\n                        right[i] += right[j]\n                        j += right[j]\n                    else: break\n\n            for i in range(0, n):\n                max_rect = max(max_rect, height[i] * (left[i] + right[i] - 1))\n\n            return max_rect\n\nNote, 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.
[]