# Untitled

unknown
c_cpp
8 days ago
1.4 kB
1
Indexable
Never
```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;
}
};```