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