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:

Advertisements

2 thoughts on “084. Largest Rectangle in Histogram

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s