## [84\. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)

- 維持 Monotonic Stack
- 如果目前的柱高大於等於 stack.top() 的柱高，將 index 推到 stack，維持 stack 放遞增柱子的 index。
- stack 需要 push 一個 `heights.push_back(0)` 補位，讓最後一個元素可以 pop() 出來。

:::spoiler Solution - Brute-force

class Solution {
public:
    int largestRectangleArea(vector<int>& heights)
    {
        int n = heights.size();
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            int area = heights[i];
            
            for (int k = i - 1; k >= 0; k--)
            {
                if (heights[k] >= heights[i])
                {
                    area += heights[i];
                }
                else break;
            }

            for (int k = i + 1; k < n; k++)
            {
                if (heights[k] >= heights[i])
                {
                    area += heights[i];
                }
                else break;
            }
            res = max(res, area);
        }
        return res;
    }
};

- 時間複雜度：$O(N^2)$
- 空間複雜度：$O(1)$
:::

:::spoiler Solution - Brute-force 2

class Solution {
public:
    int largestRectangleArea(vector<int>& heights)
    {
        int n = heights.size();
        int maxArea = 0;
        for (int i = 0; i < n; i++)
        {
            int minHeight = INT_MAX;
            for (int j = i; j < n; j++)
            {
                minHeight = min(minHeight, heights[j]);
                maxArea = max(maxArea, minHeight * (j - i + 1));
            }
        }
        return maxArea;
    }
};

- 時間複雜度：$O(N^2)$
- 空間複雜度：$O(1)$
:::

:::spoiler Solution - Stack

class Solution {
public:
    int largestRectangleArea(vector<int>& heights)
    {
        heights.push_back(0);
        
        int n = heights.size();
        
        stack<int> stk;
        
        int res = 0;
        
        int i = 0;
        
        while (i < n)
        {
            // 發現目前的柱子比 stack 裡面高的時候 => 推到 stack
            // 然後指針 i 向前移動
            // st.empty() 為空代表的意思是，上個 pop 出來的是目前最短的柱子
            if (stk.empty() || heights[i] >= heights[stk.top()])
            {
                stk.push(i);
                i++;
            }
            else
            {
                // 其餘的狀況，popup stacks 裡面的柱子計算寬度
                int h = heights[stk.top()]; stk.pop();
                int w = stk.empty() ? i : i - stk.top() - 1;
                res = max(res, h * w);
            }
        }
        return res;
    }
};

- 時間複雜度：$O(N)$
- 空間複雜度：$O(N)$
:::

:::spoiler Solution Stack 另外一種寫法

class Solution {
public:
    int largestRectangleArea(vector<int>& heights)
    {
        heights.push_back(0);
        stack<int> stk;
        int i = 0;
        int n = heights.size();
        int maxArea = 0;
        for (int i = 0; i < n; ++i)
        {
            while (!stk.empty() && heights[stk.top()] > heights[i])
            {
                int h = heights[stk.top()]; stk.pop();
                int w = stk.empty() ? i : i - stk.top() - 1;
                maxArea = max(maxArea, h * w);
            }
            stk.push(i);
        }
        return maxArea;
    }
};

- 時間複雜度：$O(N)$
- 空間複雜度：$O(N)$
:::