84.柱状图中最大的矩形

class Solution {
public:
    int largestRectangleArea(vector<int>& v) {
        int res = 0;
        vector<int>rightfirstsmallerthanmine(v.size(),v.size());
        vector<int>leftffirstsmallerthanmine(v.size(),-1);
        vector<int>s;
        for(int i=0;i<v.size();i++){
            while(!s.empty()&&v[s.back()]>v[i]){
                int idx = s.back();
                s.pop_back();
                rightfirstsmallerthanmine[idx]=i;
            }
            s.push_back(i);
        }
        s.clear();
        for(int i=v.size()-1;i>=0;i--){
            while(!s.empty()&&v[s.back()]>v[i]){
                int idx = s.back();
                s.pop_back();
                leftffirstsmallerthanmine[idx]=i;
            }
            s.push_back(i);
        }
        for(int i=0;i<v.size();i++){
            int width = rightfirstsmallerthanmine[i] - leftffirstsmallerthanmine[i]-1;
            int height = v[i];
            res = max(res, width*height);
        }
        return res; 
    }
};