largest rectangle area Algorithm
The largest rectangle area algorithm is an efficient computational method used to find the largest rectangular area that can be formed under a given histogram. This problem is particularly common in computer graphics and image processing, where it is often necessary to identify the largest rectangular region in a raster grid with certain properties. The algorithm works by iterating through each bar in the histogram and calculating the area of the rectangle that can be formed using the current bar as the smallest height. The overall largest rectangular area is updated whenever a larger area is found during the iteration process.
One popular approach to implement the largest rectangle area algorithm is to use a stack data structure. In this method, the index of each bar in the histogram is pushed onto the stack while the heights of the bars are in increasing order. When a bar with a smaller height is encountered, the algorithm starts to pop elements from the stack and calculate the area of the rectangle formed using the height of the popped element as the smallest height. This process continues until the stack is empty or the height of the current bar is greater than the height of the bar at the top of the stack. After traversing the entire histogram, any remaining elements in the stack are popped, and their corresponding areas are calculated in a similar manner. The largest area found throughout this process would be the largest rectangular area that can be formed under the given histogram.
/**
*
*@gaurav yadav
Maintain a stack
a. If stack is empty heights[stack.top()] <= heights[i])
push this i into stack.
b. Else keep popooing from stack till value at i at top of stack is
less than value at current index.
c. While popping calculate area
if stack is empty
area = i * heights[top];
it means that till this point value just removed has to be smallest element
if stack is not empty
area = heights[top] * (i - stack.top() - 1);
* Finally return maxArea
* Time complexity is O(n)
* Space complexity is O(n)
*/
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int area = 0;
int maxArea = 0;
stack <int> s;
int i;
for (i = 0; i < heights.size();) {
if (s.empty() || heights[s.top()] <= heights[i]) {
s.push(i++);
}
else {
int top = s.top();
s.pop();
if (s.empty()) {
area = i * heights[top];
}
else {
area = heights[top] * (i- s.top() -1);
}
if (area > maxArea)
maxArea = area;
}
}
while (!s.empty()) {
int top = s.top();
s.pop();
if (s.empty()) {
area = i * heights[top];
}
else {
area = heights[top] * (i- s.top() -1);
}
if (area > maxArea)
maxArea = area;
}
return maxArea;
}
};
