# 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

# Solution

Approach 1: Stack.

Approach 2: (Time Limit Exceeded) Iteration.

Approach 3: (Time Limit Exceeded) Divide and conquer.

# Code (Python)

Approach 1:

Approach 2:

# Code (C++)

Approach 1:

// Stack.
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int maxRect = 0;
        for (int i = 0; i <= heights.size(); ++i)
        {
            while (!st.empty() && (i == heights.size() || heights[st.top()] > heights[i]))
            {
                int j = st.top();
                st.pop();
                int len = (!st.empty()) ? (i - st.top() - 1) : (i - 0);
                maxRect = std::max(maxRect, heights[j] * len);
            }
            st.push(i);
        }
        return maxRect;
    }
};

Approach 2:

// Time Limit Exceeded.
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int maxRect = 0;
        for (int i = 0; i < heights.size(); ++i)
        {
            int rect = heights[i];
            int j = i - 1;
            for (; j >= 0; --j)
            {
                if (heights[j] < heights[i])
                    break;
            }
            rect += heights[i] * (i - j - 1);
            j = i + 1;
            for (; j < heights.size(); ++j)
            {
                if (heights[j] < heights[i])
                    break;
            }
            rect += heights[i] * (j - i - 1);
            maxRect = std::max(maxRect, rect);
        }
        return maxRect;
    }
};

Approach 3:

// Time Limit Exceeded.
// Divide and conquer.
class Solution {
private:
    int doLargestRectangleArea(vector<int>& heights, int head, int tail) {
        if (head > tail)
            return 0;
        int minIdx = head;
        for (int i = head+1; i <= tail; ++i)
        {
            if (heights[i] < heights[minIdx])
                minIdx = i;
        }
        return std::max(heights[minIdx] * (tail - head + 1),
            std::max(
                doLargestRectangleArea(heights, head, minIdx-1),
                doLargestRectangleArea(heights, minIdx+1, tail)));
    }
public:
    int largestRectangleArea(vector<int>& heights) {
        return doLargestRectangleArea(heights, 0, heights.size() - 1);
    }
};