C# largest rectangle in histogram

// C++ program to find maximum rectangular area in
// linear time
#include<bits/stdc++.h>
using namespace std;
 
// The main function to find the maximum rectangular
// area under given histogram with n bars
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; // Initialize 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
            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;
}
 
// Driver program to test above function
int main()
{
    int hist[] = {6, 2, 5, 4, 5, 1, 6};
    int n = sizeof(hist)/sizeof(hist[0]);
    cout << "Maximum area is " << getMaxArea(hist, n);
    return 0;
}

#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));
    }

}