class Solution(object): # Helper function calculating how far each bar can be extended to the right. def calmax(self, height): stack =  n = len(height) rec =  * n for i in xrange(len(height)): while len(stack) > 0 and height[stack[-1]] > height[i]: top = stack.pop() rec[top] = i stack.append(i) for i in stack: rec[i] = n return rec def largestRectangleArea(self, height): # How far can each bar be extended to the right? rec1 = self.calmax(height) # How far can each bar be extended to the left? rec2 = self.calmax(height[::-1])[::-1] maxa = 0 n = len(height) for i in xrange(n): # Add the left and right part together new = height[i] * (rec1[i] + rec2[i] - n) maxa = max(new, maxa) return maxa
This solution can be made faster. But who cares if the complexity is still \Theta(n)?