84. Largest Rectangle in Histogram

• Difficulty: Hard

• Topics: Array, Stack

• Similar Questions:

  • Maximal Rectangle

Problem:

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

Solutions:

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        heights.push_back(0);
        stack<int> stk;
        int area = 0;

        for (int i = 0; i < heights.size(); ++i) {
            while (!stk.empty() && heights[stk.top()] > heights[i]) {
                int topIndex = stk.top();
                stk.pop();
                area = max(area, heights[topIndex] * (i - (stk.empty() ? 0 : stk.top() + 1)));
                //cout << area << endl;
            }

            stk.push(i);
        }

        return area;
    }
};