Largest Rectangle in Histogram

We first create a variable, ‘maximumArea’, and assign it the value of the maximum area of the histogram.
Later, run two nested loops: one counting from 0 until i = N, and the other counting from j = 0 to j = N.
For each ‘jth’ iteration of this loop, we count ‘k’ from i = k until k = j and find the height of the lowest bar among them.
The area of the histogram would be ‘mininumHeight * (j-i+1)’
Maximize ‘maximumArea’

Initialize stack ‘S’ and push the top index of A[] onto ‘S’
Traverse via A[] and compare the height of each element with the height of each element on top of ‘S’
If A[i]>= A[S.top()], then push it into the S
Else A[i] <= A[S.top()], then pop the elements until A[i]>= A[S.top()]
This ensures that A[S.top()] stays at its maximum height as elements are being added to it from above and below
Lastly, push i for every item currently on S into the stack, followed by popping from S until S has no elements left in it.
Return maximum element

#include 
#include 
#include 
#include 
#include  //For using min/max function.
//Above are the libraries that has been used.

using namespace std;

class largestRectangleArea {
public:
    int largestAreaInHistogram(vector<int>& histogram) {
        int n = histogram.size(); //It stores the size of histogram vector.
        if(n == 0) return 0;
        // Create an empty stack. The stack holds indexes of histogram vector.
        stack<int> st;
        st.push(-1);
        int maxarea=0;
        //Iterating over the histogram vector for finding the maximum area.
        for(int i=0;i<n;i++){
            //st.size()>1 because -1 is stored initially and size of stack is 1
            while(st.size()!=1 && histogram[st.top()]>=histogram[i]){
                int len = histogram[st.top()];
                st.pop();
                //computing the width of the rectangle forming in histogram
                int width = i-st.top()-1;
                // if the area (len*width) of the rectangle forming in histogram is greater than previous maxarea then maxarea gets updated to the greater area
                maxarea=max(maxarea,len*width);
            }
            //Pushing index in stack it helps in calculating width
            st.push(i);
        }
        //Calculating area for all the elements left in stack if it is greater than previous maxarea then update maxarea
        while(st.size()!=1){
            int in=st.top();
            st.pop();
            int w = n-st.top() -1;
            int h = histogram[in];
            maxarea = max(maxarea,w*h);
        }
        return maxarea;
    }
};

int main()
{
    vector<int>hist{5, 6, 4, 3, 7, 5};
    largestRectangleArea ob;
    cout << "Maximum area is " << ob.largestAreaInHistogram(hist);
    return 0;
}

import java.util.Stack;

public class largestAreaInHistogram {
    private static int largestAreaInHistogram(int[] heights){
        Stack<Integer> st=new Stack<>();
        st.push(-1);
        int maxArea=0;

        //Iterating over the height array for finding the max area.
        for(int i=0;i<heights.length;i++){
            //Height of top element of stack should be greater than current element height
            while(st.size()!=1 && st.peek()!=-1 && heights[st.peek()]>=heights[i]){
                int currheight=heights[st.peek()];
                st.pop();
                //Calculating the width of the rectangle
                int width=i-st.peek()-1;
                //if currheight*width (Area) is greater than previous maxArea
                // then update maxArea
                maxArea=Math.max(maxArea,currheight*width);
            }
            //Pushing each element in stack to calculate area
            st.push(i);
        }
        //Computing area for all the elements left in stack
        while(st.size()!=1){
            int idx=st.pop();
            int w=heights.length-st.peek()-1;
            int h=heights[idx];
            maxArea=Math.max(maxArea,w*h);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[] height={5, 6, 4, 3, 7, 5};
        System.out.println("Maximum area is "+largestAreaInHistogram(height));
    }

}

def largestAreaInHistogram(height):
    stack = [-1]
    maxArea = 0
    for i in range(len(height)):
        while stack[-1] != -1 and height[stack[-1]] >= height[i]:
            currentHeight = height[stack.pop()]
            currentWidth = i - stack[-1] - 1
            maxArea = max(maxArea, currentHeight * currentWidth)
        stack.append(i)
 
    while stack[-1] != -1:
        currentHeight = height[stack.pop()]
        currentWidth = len(height) - stack[-1] - 1
        maxArea = max(maxArea, currentHeight * currentWidth)
    return maxArea

height = [5, 6, 4, 3, 7, 5]
print("Maximum area is", largestAreaInHistogram(height))

Maximum area is 18