My c++ solution AC 13ms


  • 0
    class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            heights.push_back(0);
            vector<int> record;
            record.push_back(-1);
            record.push_back(0);
            int max=0;
            for(int i=1;i<heights.size();i++){
                if(heights[i]>heights[record.back()]) record.push_back(i);
                else{
                    while(record.size()>1&&heights[record.back()]>=heights[i]){
                       int temp=heights[record.back()];
                        record.pop_back();
                        if(max<(i-record.back()-1)*temp) {
                           // cout<<"left= "<<record.back()+1<<" right= "<<i-1<<endl;
                            max=(i-record.back()-1)*temp;}
                    }
                    record.push_back(i);
                }
                //for(auto x:record) cout<<x<<" ";
                //cout<<endl;
            }  
            return max;
            
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.