To find the largest rectangle in a histogram, we determine the
left and right boundaries for each bar. For each bar, we calculate the
maximum area it can form
by
extending to the
left and right until a
smaller bar is
encountered. This is done using two arrays:
left and
right, which store the
indices of the
first smaller bar to the
left and right of each bar, respectively. The area for each
bar is calculated as
height[i] * (right[i] - left[i] - 1).
Finally, we iterate through the
histogram to compute the area for each bar and return the one with maximum area.
class Solution { public: int largestRectangleArea(vector<int>& heights) { int sz = heights.size(); if(sz==1) return heights[0]; int left[sz]; int right[sz]; left[0] = -1; right[sz-1] = sz; for(int i=1;i<sz;i++){ int p = i-1; while(p>=0 && heights[i] <= heights[p]) p = left[p]; left[i] = p; } for(int i=sz-2;i>=0;i--){ int p = i+1; while(p<sz && heights[i]<= heights[p]) p = right[p]; right[i] = p; } int ans = INT_MIN; for(int i=0;i<sz;i++){ int area = heights[i]*(right[i]-left[i]-1); ans = max(area,ans); } return ans; } };
The algorithm processes each bar in the histogram once, where 'n'
is the number of
bars.
The algorithm uses two additional arrays of size 'n' to
store the left and right boundaries.