LeetCode Problem : Largest Rectangle in Histogram

Problem

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Code

int largestRectangleArea(vector<int> &A) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
    int n = A.size();
    if(n == 0)
        return 0;
    vector<int> left(n,0),right(n,0);
    int max_area = 0;
    right[n - 1] = n - 1;
    for(int i = 1;i < n; ++i){
        if(A[i] > A[i - 1])
            left[i] = i;
        else{
            int j = left[i - 1];
            while(j > 0 && A[i] <= A[j - 1])
            --j;
            left[i] = j;
        }
    }
    for(int i = n - 2;i >= 0; --i){
        if(A[i] > A[i + 1])
            right[i] = i;
        else{
            int j = right[i + 1];
            while(j < n - 1 && A[i] <= A[j + 1])
            ++j;
            right[i] = j;
        }
    }
    for(int i = 0;i < n; ++i){
        int area = A[i]*(right[i] - left[i] + 1);
        if(max_area < area)
        max_area = area;
    }
    return max_area;
}