Largest rectangle in a histogram with precomputation

largest-rectangle-in-histogram-precompute.cpp

int largestRectangleArea(vector<int> &A) {
    int n = A.size();
    vector<int> posLeft(n);
    stack<int> S;
    for (int i = 0; i < n; i++) {
        while (!S.empty() && A[S.top()] >= A[i])
            S.pop();
        posLeft[i] = S.empty() ? 0 : S.top() + 1;
        S.push(i);
    }
    
    vector<int> posRight(n);
    while (!S.empty()) S.pop();
    for (int i = n-1; i >= 0; i--) {
        while (!S.empty() && A[S.top()] >= A[i])
            S.pop();
        posRight[i] = S.empty() ? n-1 : S.top() - 1;
        S.push(i);
    }
    
    int maxArea = 0;
    for (int i = 0; i < n; i++)
        maxArea = max(maxArea, (posRight[i] - posLeft[i] + 1) * A[i]);
    return maxArea;
}