largest-rectangle-in-histogram

84. Largest Rectangle in Histogram

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

T: $O(N^2)$
S: $O(1)$
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;
    }
};

T: $O(N^2)$
S: $O(1)$
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;
    }
};

T: $O(N)$
S: $O(N)$

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

T: $O(N)$
S: $O(N)$

84. Largest Rectangle in Histogram​

84. Largest Rectangle in Histogram