• 分類(lèi)：Stack
• 時(shí)間復(fù)雜度: O(n)
• 空間復(fù)雜度: O(n)

84. Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

image.png

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

image.png

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]

Output: 10

代碼1：

class Solution:
    def largestRectangleArea(self, heights: 'List[int]') -> 'int':
        if heights==None or len(heights)==0:
            return 0

        res=0
        j=0
        stack=[]
        left=0
        right=0
        heights.append(0)
        heights.insert(0,0)
        for i in range(0,len(heights)):
            if len(stack)==0 or heights[i]>heights[stack[-1]]:
                stack.append(i)
            else:
                right=i
                j=stack[-1]
                while len(stack)>1 and heights[stack[-1]]>heights[right]:
                    h=heights[stack.pop()]
                    left=stack[-1]
                    res=max(res,h*(right-left-1))
                stack.append(i)

        return res

代碼2：

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:

        res = 0
        if heights == None or len(heights)==0:
            return res

        stack = list()
        stack.append(-1)
        for i in range(len(heights)):
            while(stack[-1]!=-1 and heights[stack[-1]]>=heights[i]):
                h = heights[stack.pop()]
                res = max(res, (i-stack[-1]-1)*h)
            stack.append(i)

        while (stack[-1]!=-1):
            h = heights[stack.pop()]
            res = max(res,(len(heights)-stack[-1]-1)*h)


        return res

討論：

1.看的youtube的籃子王的講解
2.我是兩邊直接加兩個(gè)0避免了還要比較邊界條件的情況？？？代碼可以更straight forward？？？
3.別忘了比完了之后那個(gè)地方的點(diǎn)是要加回去的orz
4.今天寫(xiě)代碼是看youtube上一個(gè)happygirl的博主。感覺(jué)思路比籃子王清楚。還是個(gè)單調(diào)遞增棧