Largest rectangle in a histogram best solution

largest-rectangle-in-histogram-best.cpp

int largestRectangleArea(vector<int> &A) {
    A.push_back(0); // sentinel to ensure all indices get popped off the stack
    stack<int> S;
    int maxArea = 0;
    for (int i = 0; i < A.size(); i++) {
        while (!S.empty() && A[S.top()] >= A[i]) {
            int height = A[S.top()];
            S.pop();
            int left = S.empty() ? 0 : S.top() + 1, right = i - 1;
            maxArea = max(maxArea, (right - left + 1) * height);
        }
        S.push(i);
    }
    return maxArea;
}