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(int[] heights) { int sz = heights.length; int[] nsL = new int[sz]; // Nearest smaller bar in left int[] nsR = new int[sz]; // Nearest smaller bar in right for(int i=0;i<sz;i++){ int p = i-1; while(p>=0 && heights[i] <= heights[p]) p = nsL[p]; // Here, we're using the previously calculated value for leftMax for Pth bar nsL[i] = p; // It's the index of 1st bar in left whose height is just less than height[i] } for(int i=sz-1;i>=0;i--){ int p = i+1; while(p<sz && heights[i] <= heights[p]) p = nsR[p]; // Here, we're using the previously calculated value for rightMax for Pth bar nsR[i] = p; // It's the index of 1st bar in right whose height is just less than height[i] } int mxArea = 0; for(int i=0;i<sz;i++){ int width = Math.abs(nsL[i]-nsR[i])-1; int area = width*heights[i]; mxArea = Math.max(area,mxArea); } return mxArea; } }
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.