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.
BR approach:
/*
* goal is to find a largest rectangle area
* rectangle are is = common height * width.
* at each element, this area varies based on height.
* Minimum height should be maintained to compute the
* area across heights.
* Brute force approach is:
* for each element of height
* compute area among all the remaining elements
* save the max area
*/
int largestRectangleArea(int* heights, int hs){
int ii, jj, ma=0;
printf("int max %x (%d), int min %x(%d)\n",INT_MAX, INT_MAX, INT_MIN, INT_MIN);
for (ii=0; ii<hs; ii++){
int min =INT_MAX, area;
for (jj=ii; jj<hs; jj++){
if (min > heights[jj])
min = heights[jj];
area = min *(jj-ii+1);
if (ma < area)
ma = area;
}
}
return ma;
}mono stack approach:
/*
* goal is to find a largest rectangle area
* rectangle are is = common height * width.
* at each element, this area varies based on height.
* Minimum height should be maintained to compute the
* area across heights.
* Use monostack to reduce time complexity
* Push the index of the element in stack if stack empty
* if the element > top
* else pop element index compute the area, update the max area if computed area is bigger.
*/
int largestRectangleArea(int* heights, int hs){
int ii=0, ma=0;
int area;
int st[hs+1], ss=1;
st[0] =-1;
while (ii<hs){
/* if stack empty or current is bigger than top, push and proceed
st[0] assigned to -1,
if empty this condition satisfies*/
if ((ss==1) || (heights[st[ss-1]] < heights[ii])){
st[ss++] = ii; ii++; continue;
}
/* if not bigger , pop till bigger values or
empty */
area = heights[st[ss-1]] * (ii-st[ss-2]-1);
if (area > ma)
ma = area;
ss--;
}
while (ss>=2){
area = heights[st[ss-1]] * (hs-st[ss-2]-1);
if (area > ma)
ma = area;
ss--;
} return ma;
}
More understanding is required on monostack. As of now what I understood is if a problem stmt contains number comparisons monostack is useful.
