Untitled

class Solution {
public:
    vector<int> nextSmallestRight(vector<int>& heights) {
        int n = heights.size();
        vector<int> ans(n, -1);
        stack<int> st;
        for(int i=0 ; i<n ; i++) {
            while (!st.empty() and heights[st.top()] > heights[i]) {
                ans[st.top()] = i;
                st.pop();
            }
            st.push(i);
        }
        return ans;
    }

    vector<int> nextSmallestLeft(vector<int>& heights) {
        int n = heights.size();
        vector<int> ans(n, -1);
        stack<int> st;
        for(int i=n-1 ; i>=0 ; i--) {
            while (!st.empty() and heights[st.top()] > heights[i]) {
                ans[st.top()] = i;
                st.pop();
            }
            st.push(i);
        }
        return ans;
    }

    int largestRectangleArea(vector<int>& heights) {
        vector<int> nxtSmallerEleRight = nextSmallestRight(heights);
        vector<int> nxtSmallerEleLeft = nextSmallestLeft(heights);
        int ans = -1;
        for(int i=0 ; i<heights.size() ; i++) {
            int fromRight = nxtSmallerEleRight[i] != -1 ?  heights[i]*(nxtSmallerEleRight[i] - i) : 0;
            int fromLeft = nxtSmallerEleLeft[i] != -1 ?  heights[i]*(i - nxtSmallerEleLeft[i]) : 0;
            int currAns = fromRight + fromLeft - heights[i];
            ans = max(ans, currAns);
        }
        return ans;
    }
};