Untitled
unknown
plain_text
a year ago
1.2 kB
0
Indexable
Never
#include<stack> vector<int> nextsmallelement(vector<int> arr, int n){ // a vector containing next stack<int> s; // small element for every index s.push(-1); vector<int> ans(n); for(int i=n-1;i>=0;i--){ int curr=arr[i]; while(s.top()!= -1 && arr[s.top()]>=curr){ // to avoid arr[-1] s.pop(); } ans[i]=s.top(); s.push(i); //s now has index } return ans; } vector<int> prevsmallelement(vector<int> arr, int n){ stack<int> s; s.push(-1); vector<int> ans(n); for(int i=0;i<n;i++){ int curr=arr[i]; while(s.top()!= -1 && arr[s.top()]>=curr){ s.pop(); } ans[i]=s.top(); s.push(i); //s now has index } return ans; } int largestRectangle(vector < int > & heights) { int n=heights.size(); int ansarea=0; vector<int> nextsmall(n); vector<int> prevsmall(n); nextsmall=nextsmallelement(heights,n); prevsmall =prevsmallelement(heights,n); for(int i=0;i<n;i++){ if(nextsmall[i]==-1) nextsmall[i]=n; int w=nextsmall[i]-prevsmall[i] -1; int area= heights[i] * w; ansarea=max(area,ansarea); } return ansarea; }