Maximum Rectangular Area in a Histogram

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have the same width and the width is 1 unit, there will be N bars height of each bar will be given by the array arr.

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

c++

class Solution {
public:
    //Function to find largest rectangular area possible in a given histogram.
    long long getMaxArea(long long arr[], int n) {
        vector<pair<long long, long long>> st;
        long long res = 0;
        for(int i = 0; i < n; i++) {
            int left = i;
            while(!st.empty() and st.back().second >= arr[i]) {
                res = max(res, (i - st.back().first) * st.back().second);
                left = st.back().first;
                st.pop_back();
            }
            st.push_back({left, arr[i]});
        }
        for(int i = 0; i < st.size(); i++) {
            res = max(res, (n - st[i].first) * st[i].second);
        }
        
        return res;
    }
};