Largest Rectangle in Histogram

Paste_Image.png

求连续矩形最大面积，抓住一点，当如果有顺序的时候很容易求得结果，过意可以借助于栈来调整为有顺序。参考网上的解法。
自己用动态规划实现了一下，时间还超限。

class Solution(object):
    """
    :type heights: List[int]
    :rtype: int
    """
    def largestRectangleArea(self, heights):
        if len(heights) == 0:
            return 0
        stack = [heights[0]]
        Max = 0
        for i in range(1,len(heights)):
            #按照升序序列
            if heights[i] >= stack[-1]:
                stack.append(heights[i])
            else:#将序
                temp = stack.pop()
                Max = max(Max,temp)
                index = 1
                while len(stack)!=0 and stack[-1] > heights[i]:
                    temp = stack.pop()
                    index += 1
                    Max=max(temp*index ,Max)
                for j in range(index+1):
                    stack.append(heights[i])
        for i in range(len(stack)):
            Max = max(Max,stack[i]*(len(stack)-i))
        return Max

动态规划

class Solution(object):
    """
    :type heights: List[int]
    :rtype: int
    """
    def largestRectangleArea(self, heights):
        L = []
        Max = 0
        for i in range(len(heights)):
            L.append([])
            for j in range(1,heights[i]+1):
                if i==0:
                    t = j
                    L[i].append(t)
                else:
                    if len(L[i-1]) < j:
                        t = j
                        L[i].append(t)
                    else:
                        t = j+L[i-1][j-1]
                        L[i].append(t)
                if ( t > Max):
                    Max = t
        return Max


s= Solution()
print(s.largestRectangleArea([2,1,5,6,2,3]))