> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/84.-largest-rectangle-in-histogram.md).

# 84. Largest Rectangle in Histogram

## 1.問題 

* 給予n個整數代表長方形bar的高度, 找出最大面積的長方形

![](/files/-LNcyo9TuX-jjWGnrc4P)

![](/files/-LNcyuOB59fCosB_M4Px)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
  * 確認題意:  將輸入的兩個字串轉為數字相乘並返回對應的字串
* function header, parameter
* test input
* 說明想法
  * 為了能夠保留最高的bar, 用stack存取: 當height\[i] > stack.top時push, 反之開始計算最大面積
  * 最大面積有兩種情形
    \*
    1. stack.top到i - 1的面積 (不包含height\[i])
    2. height\[i]到stack.top的面積
    3. height\[i]自己
  * 若stack內還有東西, 則計算stack內每個bar為基準時的面積 &#x20;
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if (heights.size() == 0) {
            return 0;
        }
        
        int n = heights.size(), area = INT_MIN;
        for (int i = 0; i < n; i++) {
            if (i + 1 < heights.size() && heights[i] <= heights[i + 1]) {
                continue;
            }
            int minH = heights[i];
            for (int j = i; j >= 0; j--) {
                minH = min(minH, heights[j]);
                int tmpArea = minH * (i - j + 1);
                area = max(area, tmpArea);
            }
        }
        
        return area;
    }
};
```