Largest Rectanglein Histogram Algorithm

The Largest Rectangle in Histogram Algorithm is an important and widely used algorithm in computer science, specifically in the field of data structure and algorithms. It is primarily designed to find the largest rectangular area within a given histogram, which can be represented as a series of adjacent bars or rectangles of varying heights. The algorithm's primary goal is to find the maximum possible area that can be formed by combining one or more of these adjacent bars or rectangles. This problem is often encountered in various applications such as image processing, computational geometry, and even stock market analysis where the largest area under the curve could represent the maximum profit that can be obtained. The algorithm works by using a stack-based approach, which allows for efficient processing of the input data. It starts by iterating through each bar or rectangle in the histogram and pushing their indices onto a stack if the height of the current bar is greater than the height of the bar at the index on the top of the stack. If the height of the current bar is less than or equal to the height of the bar at the index on the top of the stack, the algorithm pops elements from the stack until it encounters a bar with a height less than the current bar. While popping elements from the stack, the algorithm calculates the area of the rectangle that can be formed using the popped bar's height as the height and the difference between the current index and the index at the top of the stack as the width. The maximum area encountered during this process is the largest rectangular area in the histogram. This algorithm has a time complexity of O(n), where n is the number of bars in the histogram, making it an efficient and effective solution for finding the largest rectangle in a histogram.
class Solution {
public:
    int largestRectangleArea(vector<int>& height) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        
        int n = height.size();
        int width[n];
        stack<int> minHeight;
        
        for (int i = 0; i < n; i++) {
            while (!minHeight.empty() && height[i] <= height[minHeight.top()])
                minHeight.pop();
            int left = minHeight.empty() ? -1 : minHeight.top();
            width[i] = i - left - 1;
            minHeight.push(i);
        }
        
        while (!minHeight.empty())
            minHeight.pop();
            
        for (int i = n - 1; i >= 0; i--) {
            while (!minHeight.empty() && height[i] <= height[minHeight.top()])
                minHeight.pop();
            int right = minHeight.empty() ? n : minHeight.top();
            width[i] += right - i - 1;
            minHeight.push(i);
        }
        
        int result = 0;
        for (int i = 0; i < n; i++) 
            result = max(result, height[i] * (width[i] + 1));
        return result;
    }
};

LANGUAGE:

DARK MODE: