python写算法题：leetcode: 84. Largest Rectangle in Histogram_python 84. largest rectangle in histogram

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) and not left<=sortHeight[ind][0]<right:
            ind+=1
        if 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))