84. Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Example:

Input: [2,1,5,6,2,3]
Output: 10

每一個i和i + 1的高度比較，如果i的高度大於i + 1的高度，那麼就從這個位置i開始計算。然後從i往前試各種介於0~i之間的高度所形成的結果。

// Brute force with pruning
int largestRectangleArea(vector<int>& heights) { // time: O(n^2); space: O(1)
    int res = 0;
    for (int i = 0; i < heights.size(); ++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]);
            res = max(res, minH * (i - j + 1));
        }
    }
    return res;
}

利用一個monotonic increasing stack來紀錄indices，當發現一個i的高度大於stack中最大的index的高度時，就可以利用stack的top的高度來開始形成長方形。記得這邊要讓i的值decrement，因為每一個for iteration都會讓i的值increment。

// Monotone Stack
int largestRectangleArea(vector<int>& heights) { // time: O(n); space: O(n)
    int res = 0;
    stack<int> st;
    heights.push_back(0);
    for (int i = 0; i < heights.size(); ++i) {
        if (st.empty() || heights[st.top()] < heights[i]) {
            st.push(i);
        } else {
            int cur = st.top(); st.pop();
            res = max(res, heights[cur] * (st.empty() ? i : i - st.top() - 1));
            --i;
        }
    }
    return res;
}

// Monotonic Stack
int largestRectangleArea(vector<int>& heights) { // time: O(n); space: O(n)
    int res = 0;
    stack<int> st;
    heights.push_back(0);
    for (int i = 0; i < heights.size(); ++i) {
        while (!st.empty() && heights[st.top()] >= heights[i]) {
            int cur = st.top(); st.pop();
            res = max(res, heights[cur] * (st.empty() ? i : i - st.top() - 1));
        }
        st.push(i);
    }
    return res;
}