class Solution(object):
def _largestArea(self, sortHeight, ind, heights, left, right):
if right<=left:
return 0
if right-left<=1:
return heights[left]*(right-left)
while ind=len(sortHeight):
return 0
return max((right-left)*sortHeight[ind][1],
self._largestArea(sortHeight, ind+1, heights, left, sortHeight[ind][0]),
self._largestArea(sortHeight, ind+1, heights, sortHeight[ind][0]+1, right)
)
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int
"""
sortHeights = sorted([v for v in enumerate(heights)], key=lambda x:x[1])
return self._largestArea(sortHeights, 0, heights, 0, len(sortHeights))