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 =  * n right =  * 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.