Largest Rectangle in Histogram

                            Solution in C :

#define max(a, b) a>b?a:b
// C program for array implementation of stack
// A structure to represent a stack
struct Stack
{
    int top;
    unsigned capacity;
    int* array;
};
 
// function to create a stack of given capacity. It initializes size of
// stack as 0
struct Stack* createStack(unsigned capacity)
{
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*) malloc(stack->capacity * sizeof(int));
    return stack;
}
 
// Stack is full when top is equal to the last index
int isFull(struct Stack* stack)
{   return stack->top == stack->capacity - 1; }
 
// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{   return stack->top == -1;  }
 
// Function to add an item to stack.  It increases top by 1
void push(struct Stack* stack, int item)
{
    if (isFull(stack))
        return;
    stack->array[++stack->top] = item;
    //printf("%d pushed to stack\n", item);
}
 
// Function to remove an item from stack.  It decreases top by 1
int pop(struct Stack* stack)
{
    if (isEmpty(stack))
        return INT_MIN;
    return stack->array[stack->top--];
}

// Function to return the last item from stack
int back(struct Stack* stack)
{
    if (isEmpty(stack))
        return INT_MIN;
    return stack->array[stack->top];
}

int largestRectangleArea(int* heights, int heightsSize) {
    // 在heights数组后增加一个高度为0的bar
    heightsSize += 1;
    //realloc(heights, sizeof(int)*heightsSize);
    //heights[heightsSize-1] = 0;
    int* tempArray = (int*)malloc(sizeof(int)*heightsSize);
    for(int j=0; j<heightsSize-1; j++)
        tempArray[j] = heights[j];
    tempArray[heightsSize-1] = 0;
    struct Stack* stack = createStack(heightsSize);
    int sum = 0;
    int i = 0;
    while(i < heightsSize) {
        if(isEmpty(stack) || tempArray[i] > tempArray[back(stack)]) {
            push(stack, i);
            i++;
        } else {
            int t = back(stack);
            //printf("%d\n", t);
            pop(stack);
            // stack为空的情况
            int temp = tempArray[t]*(isEmpty(stack)?i:i-back(stack)-1);
            sum = max(sum, temp);
        }
    }
    free(tempArray);
    return sum;
}
                        

                        Solution in C++ :

class Solution {
public:
    int largestRectangleArea(vector<int>& heights){
        int n=heights.size();
        vector<int> nsr(n,0);
        vector<int> nsl(n,0);

        stack<int> s;

        for(int i=n-1;i>=0;i--){
            while(!s.empty() && heights[i]<=heights[s.top()]){
                s.pop();
            }
            if(s.empty()) nsr[i]=n;
            else nsr[i]=s.top();
            s.push(i);
        }

        while(!s.empty()) s.pop();

        for(int i=0;i<n;i++){
            while(!s.empty() && heights[i]<=heights[s.top()]){
                s.pop();
            }
            if(s.empty()) nsl[i]=-1;
            else nsl[i]=s.top();
            s.push(i);
        }

        int ans=0;

        for(int i=0;i<n;i++){
            ans=max(ans, heights[i]*(nsr[i]-nsl[i]-1));
        }
        return ans;        
    }
};
                    

                        Solution in Java :

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] nsr = new int[n];
        int[] nsl = new int[n];
        
        Stack<Integer> s = new Stack<>();

        for (int i = n - 1; i >= 0; i--) {
            while (!s.isEmpty() && heights[i] <= heights[s.peek()]) {
                s.pop();
            }
            if (s.isEmpty()) nsr[i] = n;
            else nsr[i] = s.peek();
            s.push(i);
        }

        while (!s.isEmpty()) s.pop();

        for (int i = 0; i < n; i++) {
            while (!s.isEmpty() && heights[i] <= heights[s.peek()]) {
                s.pop();
            }
            if (s.isEmpty()) nsl[i] = -1;
            else nsl[i] = s.peek();
            s.push(i);
        }

        int ans = 0;

        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, heights[i] * (nsr[i] - nsl[i] - 1));
        }
        return ans;
    }
}
                    

                        Solution in Python : 
                            
class Solution(object):
    def largestRectangleArea(self, heights):
        n = len(heights)
        nsr = [0] * n
        nsl = [0] * n

        s = []

        for i in range(n - 1, -1, -1):
            while s and heights[i] <= heights[s[-1]]:
                s.pop()
            if not s:
                nsr[i] = n
            else:
                nsr[i] = s[-1]
            s.append(i)

        while s:
            s.pop()

        for i in range(n):
            while s and heights[i] <= heights[s[-1]]:
                s.pop()
            if not s:
                nsl[i] = -1
            else:
                nsl[i] = s[-1]
            s.append(i)

        ans = 0

        for i in range(n):
            ans = max(ans, heights[i] * (nsr[i] - nsl[i] - 1))
        return ans