Problem Statement

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Problem Link

Largest Rectangle in Histogram - LeetCode

Reference Video

https://www.youtube.com/watch?v=MhQPpAoZbMc&ab_channel=CodingBlocks

Code

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        
        int n = heights.size();
        stack<int> s;
        int area,maxarea = 0;
        int i;
        for(i=0;i<n;) {
            
            if(s.empty()||heights[s.top()]<=heights[i])
                s.push(i++);// push higher bar above the lower onto the stack
            
            else
            {
                while(!s.empty()&&heights[s.top()]>heights[i]) {
                    int top = s.top();
                    s.pop();
                    if(s.empty())
                    area = heights[top] * i;//height of curr bar * rightmost index
                    else
                    area = heights[top] * (i-s.top()-1);
                    // height of curr bar * (rightmost indexed bar smaller than curr bar 
                    // - lefttmost indexed bar smaller than curr bar - 1)
                
                    maxarea = max(area,maxarea);
                }
            }
        }
        while(!s.empty()) {
            int top = s.top();
                s.pop();
                if(s.empty())
                    area = heights[top] * i;
                else
                    area = heights[top] * (i-s.top()-1);
             
                maxarea = max(area,maxarea);
        }
        return maxarea;
    }
};
// Time Complexity : O(n)