# **Leetcode筆記(Largest Rectangle in Histogram)**

:::info
:information_source: 題目 : Largest Rectangle in Histogram, 類型 : stack , 等級 : hard
日期 : 2023/06/05，2023/06/29
:::

### 嘗試
2023/06/29
有點難，嚴格遞增stack，遇到小的pop出來，順便計算面積
不太懂我這個解法為什麼不行

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = [] # [(index, h)]
        maxArea = 0
        heights.append(0) # 最後一定要全部都pop出 所以在後面append一最小值
        for i, h in enumerate(heights):
            while stack and stack[-1][1] >= h:
                i_p, i_h = stack.pop() # 先pop掉
                width = (i - i_p)
                if not stack: # 前面全部都比較高 stack被pop完
                    width = i
                maxArea = max(maxArea, i_h * width)
            stack.append((i, h))

        return maxArea

---
### **優化**
單調遞增的stack
* 如果後面新來的元素高度比棧頂元素高，那麼需要入棧，因為面積最大的元素會出現在後面
* 如果後面新來的元素高度比棧頂元素小，那麼需要彈出棧裡的元素，每次彈出的時候都要對計算目前的寬度，相乘得到面積

使用的解法與流程請看[這裡](https://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html)

class Solution:
    def largestRectangleArea(self, heights: [int]) -> int:
        stack = []
        heights.append(0) # 最後面加0 遇到後前的的全部強制pop出
        max_area = 0

        for index, value in enumerate(heights):
            # 當stack有東西 且違反遞增原則
            # 會pop到遇到比value小的(重新回到遞增狀態)
            while stack and heights[stack[-1]] >= value:
                pre_index = stack.pop() # 前一個最高者
                width = (index - stack[-1] - 1 if stack else index) # 要減1 因為前一個最高者已經被pop出來了
                max_area = max(max_area, heights[pre_index] * width)
            # 遞增
            stack.append(index)

        return max_area

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success

:::

**思路**

**講解連結**
https://www.youtube.com/watch?v=vcv3REtIvEo&t=433s&ab_channel=Techdose
https://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html
https://blog.csdn.net/fuxuemingzhu/article/details/82977472
Provided by. Techdose(突然覺得難題印度人講的比較透徹) & lichen782 & 负雪明烛

###### tags: `stack` `hard` `leetcode` `待解`