# 084. Largest Rectangle in Histogram

Difficulty: Hard

Frequency: N/A

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.

For example,
Given heights = `[2,1,5,6,2,3]`,
return `10`.

Test Cases:

Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
```class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size(), area = 0, height, left;
stack<int> idx;
for (int i = 0; i <= n; i++) {
while (i == n || !idx.empty() && heights[idx.top()] > heights[i]) {
if (i == n && idx.empty()) {
height = 0;
i++;
} else {
height = heights[idx.top()];
idx.pop();
}
left = idx.empty() ? -1 : idx.top();
area = max(area, height * (i - left - 1));
}
idx.push(i);
}
return area;
}
};
```

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Submission errors:

Things to learn:

## 2 thoughts on “084. Largest Rectangle in Histogram”

1. […] Largest Rectangle in Histogram […]

Like