C++ || Stack Solution || Next smaller to left &Right
\t// find the index vector for next smaller to left\n\t// find the index vector for next smaller to right \n\t// width will be right[i]-left[i]-1 \n\t// here st
\t// find the index vector for next smaller to left\n\t// find the index vector for next smaller to right \n\t// width will be right[i]-left[i]-1 \n\t// here stack<pair<int,int>> first element in pair denotes height[i] and \n\t// second element of pair corresponds to index i \n\n\tclass Solution {\n\tpublic:\n\t\t// next smaller to left --> traverse from left \n\t\t// here we will assume that one building is at index -1 of 0 height\n\t\tvector<int>NSL(vector<int>h)\n\t\t{\n\t\t\tvector<int>left;\n\t\t\tstack<pair<int,int>>st;\n\t\t\tint pseudo=-1; \n\t\t\tfor(int i=0;i<h.size();i++)\n\t\t\t{\n\t\t\t\tif(st.empty())\n\t\t\t\t   left.push_back(pseudo);\n\n\t\t\t\telse if(st.size()>0 && st.top().first<h[i])\n\t\t\t\t\tleft.push_back(st.top().second);\n\n\t\t\t\telse if(st.size()>0 && st.top().first>=h[i])\n\t\t\t\t{\n\t\t\t\t\twhile(st.size()>0 && st.top().first>=h[i])\n\t\t\t\t\t\tst.pop();\n\t\t\t\t\tif(st.empty())\n\t\t\t\t\t\tleft.push_back(pseudo);\n\t\t\t\t\telse \n\t\t\t\t\t\tleft.push_back(st.top().second);\n\t\t\t\t}\n\t\t\t\tst.push({h[i],i});\n\t\t\t}\n\t\t\treturn left;\n\t\t}\n\n\t\t// next smaller to right traverse --> from right \n\t\t// here we will assume that one building is after lastmost index of 0 height\n\t\tvector<int>NSR(vector<int>h)\n\t\t{\n\t\t\tvector<int>right;\n\t\t\tstack<pair<int,int>>st;\n\t\t\tint pseudo=h.size(); \n\t\t\tfor(int i=h.size()-1;i>=0;i--)\n\t\t\t{\n\t\t\t\tif(st.empty())\n\t\t\t\t   right.push_back(pseudo);\n\t\t\t\telse if(st.size()>0 && st.top().first<h[i])\n\t\t\t\t\tright.push_back(st.top().second);\n\t\t\t\telse if(st.size()>0 && st.top().first>=h[i])\n\t\t\t\t{\n\t\t\t\t\twhile(st.size()>0 && st.top().first>=h[i])\n\t\t\t\t\t\tst.pop();\n\t\t\t\t\tif(st.empty())\n\t\t\t\t\t\tright.push_back(pseudo);\n\t\t\t\t\telse \n\t\t\t\t\t\tright.push_back(st.top().second);\n\t\t\t\t}\n\t\t\t\tst.push({h[i],i});\n\t\t\t}\n\t\t\treturn right;\n\t\t}\n\n\t\tint largestRectangleArea(vector<int>& heights) {\n\t\t\tvector<int>left=NSL(heights);\n\t\t\tvector<int>right=NSR(heights);\n\t\t\tvector<int>width;\n\t\t\treverse(right.begin(),right.end()); // reversing to get the correct order of next smaller to right\n\n\t\t\tint maxarea=-1;\n\t\t\tfor(int i=0;i<heights.size();i++)\n\t\t\t{\n\t\t\t\tint width=right[i]-left[i]-1;\n\t\t\t\tmaxarea=max(maxarea,width*heights[i]);\n\t\t\t}\n\t\t\treturn maxarea;\n\t\t}\n\t};
['Stack', 'C']