Largest Rectangle in Histogram

• Time : O(n)
• Space : O(n)

c++

int Solution::largestRectangleArea(vector<int> &A) {
    int res = 0, n = A.size();
    vector<pair<int, int>> st;
    for(int i = 0; i < n; i++) {
        if(st.empty() or st.back().second < A[i]) st.push_back({i,A[i]});
        else {
            int p = i;
            while(st.back().second >= A[i]) {
                p = st.back().first;
                res = max(res, (i - st.back().first) * st.back().second);
                st.pop_back();
            }
            st.push_back({p,A[i]});
        }
    }
    for(int i = 0; i < st.size(); i++) {
        auto [p, h] = st[i];
        res = max(res, (n-p) * h);
    }
    return res;
}