# 84. Largest Rectangle in Histogram

## 1.問題 

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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNcivxVEXEeloBWtcTW%2F-LNcyo9TuX-jjWGnrc4P%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-30%20%E4%B8%8B%E5%8D%881.36.58.png?alt=media\&token=d7d56bbc-cba4-4de7-8f0b-48e4786a347c)

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNcivxVEXEeloBWtcTW%2F-LNcyuOB59fCosB_M4Px%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-30%20%E4%B8%8B%E5%8D%881.37.06.png?alt=media\&token=e1c35f00-2538-4552-9a6c-47c97f318f82)

## 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;
    }
};
```