Largest rectangle area in histogram.

hist_largest_rect.py

def hist_largest_rect(heights):
    """ Largest Rectangle in Histogram.
    >>> hist_largest_rect([2,1,5,6,2,3])
    10
    >>> hist_largest_rect([3,3,3])
    9
    >>> hist_largest_rect([3,4,4])
    9
    >>> hist_largest_rect([1,2,3])
    4
    >>> hist_largest_rect([2,1,2])
    3
    """
    heights = [0] + heights + [0]
    indexes = []

    def happy(r):
        ret = [-1] * len(heights)
        for idx in r:
            bar = heights[idx]
            while len(indexes) > 0 and bar < heights[indexes[-1]]:
                last_idx = indexes.pop()
                ret[last_idx] = idx
            indexes.append(idx)
        return ret

    right = happy(xrange(len(heights)))
    left = happy(reversed(xrange(len(heights))))

    max_area = 0
    for i in range(1, len(heights) - 1):
        width = right[i] - left[i] - 1
        max_area = max(max_area, heights[i] * width)

    return max_area

if __name__ == '__main__':
    import doctest
    doctest.testmod()