[LeetCode] 84. Largest Rectangle in Histogram

Problem

Image linked to LeetCode problem page

Explanation

Our goal is to find the largest rectangular area that can be formed using one or more adjacent bars in a histogram. Instead of a brute-force solution that tries every possible range of bars to compute the area, we can solve the problem more efficiently using a monotonic stack.

A monotonic stack is a stack that keeps its elements in either increasing or decreasing order.

 

In this problem, we use a monotonic increasing stack, meaning the bars referenced by the stack are stored in non-decreasing height order. To calculate widths later, the stack stores indices, not heights. 

heights[stack[0]] ≤ heights[stack[1]] ≤ heights[stack[2]] ≤ ...

As we scan the histogram from left to right, we store in stack a set of bars that are that are “waiting” to find how wide they can be. Encountering a shorter bar forces it to stop extending to the right. At that moment, we pop the taller bars from the stack and compute the largest rectangle that uses the bars as the height.

 

At i=3, we pop and calculate the area of two rectangles that are taller than the current bar

After popping, the new top of the stack (if it exists) is the index of the closest bar to the left that is shorter than or equal to the popped bar. This is the left boundary of the rectangle. Using the index of the current bar as the right boundary, we can calculate the width of the rectangle. If the stack is empty, it means there is no shorter bar to the left, so the rectangle can extend all the way back to index 0.

There may be bars of same height in the stack, but they don't change the outcome

At the end of the loop, some bars that never encounter a shorter bar (to serve as the right boundary) will still be in the stack. We pretend there is a ‘ghost’ bar of height 0 forcing all remaining bars in the stack to be popped and processed using the same logic.

Solution

#include <vector>
#include <stack>
#include <algorithm>

class Solution {
public:
    int largestRectangleArea(std::vector<int>& heights) {
        int n = heights.size();
        int max_area = 0;
        std::stack<int> s; 

        for (int i = 0; i <= n; ++i) {
            // use 0 as a sentinel value at the end (i == n)
            int h_curr = (i == n) ? 0 : heights[i];

            // maintain a monotonic increasing stack
            while (!s.empty() && heights[s.top()] > h_curr) {
                int h = heights[s.top()];
                s.pop();
                int w = s.empty() ? i : (i - (s.top() + 1));
                max_area = std::max(max_area, h * w);
            }
            s.push(i);
        }
        return max_area;
    }
};