**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:**

Advertisements

[…] Largest Rectangle in Histogram […]

LikeLike

[…] Largest Rectangle in Histogram […]

LikeLike