Largest Rectangle Under Skyline

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

#include <vector>
using namespace std;

int largestRectangleUnderSkyline(vector<int> buildings) {
    vector<pair<int, int>> st{{-1,0}};
    int res = 0, n = buildings.size();
    for(int i = 0; i < n; i++) {
        int p = i;
        while(!st.empty() and st.back().second >= buildings[i]) {
            res = max(res, st.back().second * (i - st.back().first));
            p = st.back().first;
            st.pop_back();
        }
        st.push_back({p, buildings[i]});
    }
    for(int i = 0; i < st.size(); i++) {
        res = max(res, st[i].second * (n - st[i].first));
    }
    return res;
}