https://massivealgorithms.blogspot.com/2014/09/largest-rectangle-in-histogram.html
Largest Rectangular Area in a Histogram | Set 1 | GeeksforGeeks
Largest Rectangular Area in a Histogram | Set 2
Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit.
We can use Divide and Conquer to solve this in O(nLogn) time. The idea is to find the minimum value in the given array. Once we have index of the minimum value, the max area is maximum of following three values.
a) Maximum area in left side of minimum value (Not including the min value)
b) Maximum area in right side of minimum value (Not including the min value)
c) Number of bars multiplied by minimum value.
The areas in left and right of minimum value bar can be calculated recursively. If we use linear search to find the minimum value, then the worst case time complexity of this algorithm becomes O(n^2). In worst case, we always have (n-1) elements in one side and 0 elements in other side and if the finding minimum takes O(n) time, we get the recurrence similar to worst case of Quick Sort.
How to find the minimum efficiently? Range Minimum Query using Segment Tree can be used for this. We build segment tree of the given histogram heights. Once the segment tree is built, all range minimum queries take O(Logn) time.
O(nLogn) Solution:
Largest Rectangular Area in a Histogram | Set 2
For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle. If we calculate such area for every bar ‘x’ and find the maximum of all areas, our task is done. How to calculate area with ‘x’ as smallest bar? We need to know index of the first smaller (smaller than ‘x’) bar on left of ‘x’ and index of first smaller bar on right of ‘x’.
We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as smallest bar. How do we get left and right indexes of the popped bar – the current index tells us the ‘right index’ and index of previous item in stack is the ‘left index’.
Read full article from Largest Rectangular Area in a Histogram | Set 1 | GeeksforGeeks
Largest Rectangular Area in a Histogram | Set 1 | GeeksforGeeks
Largest Rectangular Area in a Histogram | Set 2
Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit.
We can use Divide and Conquer to solve this in O(nLogn) time. The idea is to find the minimum value in the given array. Once we have index of the minimum value, the max area is maximum of following three values.
a) Maximum area in left side of minimum value (Not including the min value)
b) Maximum area in right side of minimum value (Not including the min value)
c) Number of bars multiplied by minimum value.
The areas in left and right of minimum value bar can be calculated recursively. If we use linear search to find the minimum value, then the worst case time complexity of this algorithm becomes O(n^2). In worst case, we always have (n-1) elements in one side and 0 elements in other side and if the finding minimum takes O(n) time, we get the recurrence similar to worst case of Quick Sort.
How to find the minimum efficiently? Range Minimum Query using Segment Tree can be used for this. We build segment tree of the given histogram heights. Once the segment tree is built, all range minimum queries take O(Logn) time.
O(nLogn) Solution:
/* A recursive function to get the index of minimum value in a given range of indexes. The following are parameters for this function. hist --> Input array for which segment tree is built st --> Pointer to segment tree index --> Index of current node in the segment tree. Initially 0 is passed as root is always at index 0 ss & se --> Starting and ending indexes of the segment represented by current node, i.e., st[index] qs & qe --> Starting and ending indexes of query range */int RMQUtil(int *hist, int *st, int ss, int se, int qs, int qe, int index){ // If segment of this node is a part of given range, then return the // min of the segment if (qs <= ss && qe >= se) return st[index]; // If segment of this node is outside the given range if (se < qs || ss > qe) return -1; // If a part of this segment overlaps with the given range int mid = getMid(ss, se); return minVal(hist, RMQUtil(hist, st, ss, mid, qs, qe, 2*index+1), RMQUtil(hist, st, mid+1, se, qs, qe, 2*index+2));}// Return index of minimum element in range from index qs (quey start) to// qe (query end). It mainly uses RMQUtil()int RMQ(int *hist, int *st, int n, int qs, int qe){ // Check for erroneous input values if (qs < 0 || qe > n-1 || qs > qe) { cout << "Invalid Input"; return -1; } return RMQUtil(hist, st, 0, n-1, qs, qe, 0);}// A recursive function that constructs Segment Tree for hist[ss..se].// si is index of current node in segment tree stint constructSTUtil(int hist[], int ss, int se, int *st, int si){ // If there is one element in array, store it in current node of // segment tree and return if (ss == se) return (st[si] = ss); // If there are more than one elements, then recur for left and // right subtrees and store the minimum of two values in this node int mid = getMid(ss, se); st[si] = minVal(hist, constructSTUtil(hist, ss, mid, st, si*2+1), constructSTUtil(hist, mid+1, se, st, si*2+2)); return st[si];}/* Function to construct segment tree from given array. This function allocates memory for segment tree and calls constructSTUtil() to fill the allocated memory */int *constructST(int hist[], int n){ // Allocate memory for segment tree int x = (int)(ceil(log2(n))); //Height of segment tree int max_size = 2*(int)pow(2, x) - 1; //Maximum size of segment tree int *st = new int[max_size]; // Fill the allocated memory st constructSTUtil(hist, 0, n-1, st, 0); // Return the constructed segment tree return st;}int getMaxAreaRec(int *hist, int *st, int n, int l, int r){ // Base cases if (l > r) return INT_MIN; if (l == r) return hist[l]; // Find index of the minimum value in given range // This takes O(Logn)time int m = RMQ(hist, st, n, l, r); /* Return maximum of following three possible cases a) Maximum area in Left of min value (not including the min) a) Maximum area in right of min value (not including the min) c) Maximum area including min */ return max(getMaxAreaRec(hist, st, n, l, m-1), getMaxAreaRec(hist, st, n, m+1, r), (r-l+1)*(hist[m]) );}// The main function to find max areaint getMaxArea(int hist[], int n){ // Build segment tree from given array. This takes // O(n) time int *st = constructST(hist, n); // Use recursive utility function to find the // maximum area return getMaxAreaRec(hist, st, n, 0, n-1);}For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle. If we calculate such area for every bar ‘x’ and find the maximum of all areas, our task is done. How to calculate area with ‘x’ as smallest bar? We need to know index of the first smaller (smaller than ‘x’) bar on left of ‘x’ and index of first smaller bar on right of ‘x’.
We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as smallest bar. How do we get left and right indexes of the popped bar – the current index tells us the ‘right index’ and index of previous item in stack is the ‘left index’.
1) Create an empty stack.
2) Start from first bar, and do following for every bar ‘hist[i]’ where ‘i’ varies from 0 to n-1.
……a) If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack.
……b) If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).
……a) If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack.
……b) If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).
3) If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.
int getMaxArea(int hist[], int n){ // Create an empty stack. The stack holds indexes of hist[] array // The bars stored in stack are always in increasing order of their // heights. stack<int> s; int max_area = 0; // Initalize max area int tp; // To store top of stack int area_with_top; // To store area with top bar as the smallest bar // Run through all bars of given histogram int i = 0; while (i < n) { // If this bar is higher than the bar on top stack, push it to stack if (s.empty() || hist[s.top()] <= hist[i]) s.push(i++); // If this bar is lower than top of stack, then calculate area of rectangle // with stack top as the smallest (or minimum height) bar. 'i' is // 'right index' for the top and element before top in stack is 'left index' else { tp = s.top(); // store the top index s.pop(); // pop the top // Calculate the area with hist[tp] stack as smallest bar // extract this as a method area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1); // update max area, if needed if (max_area < area_with_top) max_area = area_with_top; } } // Now pop the remaining bars from stack and calculate area with every // popped bar as the smallest bar while (s.empty() == false) { tp = s.top(); s.pop(); area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1); if (max_area < area_with_top) max_area = area_with_top; } return max_area;}