###### tags: `Leetcode` `hard` `stack` `python` `Top 100 Liked Questions`

# 84. Largest Rectangle in Histogram

## [題目連結:] https://leetcode.com/problems/largest-rectangle-in-histogram/

## 題目:
Given an array of integers ```heights``` representing the histogram's bar height where the width of each bar is ```1```, return the area of the largest rectangle in the histogram.


#### [圖片來源:] https://leetcode.com/problems/largest-rectangle-in-histogram/

## 解題想法:
* 題目要求一連串矩陣中，能構成的最大矩型面積
* 流程:
* 使用stack: ex: heights=[2,5,6,1]
* 存當前矩陣高度的出現位置
* 因為需要遍歷所有高度計算面積，因此將heights額外加個0當尾
* 若新判斷的矩陣高度:
* case1: 比stack[-1]的高度更高，則可以將其位置加入stack
* stack.append(0) (heights[0]=2)
* stack.append(1) (heights[1]=5)
* stack.append(2) (heights[2]=6)
* case1目的為**希望stack中的位置對應到的heights高度為升序(由矮到高排序)**
* 這樣再最終計算面積時候，**stack[-1]即為當前的最高邊界高度，只要再算寬度即可求面積**
* case2: 比stack[-1]的高度矮，則須pop出stack的矩陣高度的位置，計算目前寬度
* 當前pos=3，heights=1 < heights[stack[-1]] (6)
* case2為while，目的為以當前矮heights為分界，計算stack中高矩陣能夠成的面積
* 求寬時候，**將目前pos訂為最右邊界**，對於那些高度heights[stack[-1]]，先將其位置從stack中pop，再以pos為基準去與stack存的剩餘位置求寬度距離
* **要先pop原因為，才能知道stack是否已經為空了**
* 若為空則寬度為pos
* 否則為pos-stack[-1]-1
* 示意圖: (字跡潦草見諒)

## Python:

class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        stack=[]
        res=float('-inf')
        heights.append(0)
        for pos in range(len(heights)):
            #存升序
            if not stack or heights[pos]>heights[stack[-1]]:
                stack.append(pos)
            else: #pop高度，求對應的寬度，更新res
                while stack and heights[pos]<=heights[stack[-1]]:
                    curH=heights[stack[-1]]
                    stack.pop()
                    curW= pos if not stack else pos-stack[-1]-1
                    res=max(res,curH*curW)
                stack.append(pos)
        return res
    
if __name__=='__main__':
    result=Solution()
    ans=result.largestRectangleArea(heights = [2,1,5,6,2,3])
    print(ans)  #10