c++ 32ms solution using simple linked list


  • 2
    W

    Main idea:
    1 list node includes "begin","end","height","next","last",and each node's "end" equals the next node's "begin",
    2 when we considering a new building, we first to find which two node including building's begin and end (may be one node),and then we reconsider the height of this nodes
    3 in 2 we may need to split or merge some nodes
    4 we put each node's begin and height as a pair to vector from head to tail
    '''
    class Solution {
    public:
    struct Node{
    int begin;
    int end;
    int height;
    Node* next;
    Node* last;

        Node(int begin_,int end_,int height_): begin(begin_),end(end_),height(height_),next(NULL),last(NULL){}
    };
    
    void Split(Node* node,int bound){
        Node* add = new Node(node->begin,bound,node->height);
        node->begin = bound;
        node->last->next = add;
        add->last = node->last;
        add->next = node;
        node->last = add;
        return ;
    }
    
    void Merge(Node* node){
        if(node->height == node->last->height){
            Node* old = node->last;
            node->begin = old->begin;
            old->last->next = node;
            node->last = old->last;
            delete(old);
        }
        return;
    }
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        vector<pair<int, int>> results;
        int num = buildings.size();
        if(num==0)
            return results;
        Node* head = new Node(0,0,0);
        head->next = new Node(buildings[0][0],buildings[0][1],buildings[0][2]);
        Node* tail = new Node(buildings[0][1],INT_MAX,0);
        head->next->last = head;
        head->next->next = tail;
        tail->last = head->next;
        Node* beginNode = head->next;
        Node* endNode = NULL;
        
        for(int i=1;i<num;i++){
            int begin = buildings[i][0];
            int end = buildings[i][1];
            int height = buildings[i][2];
    
            while(beginNode->end < begin)
                beginNode = beginNode->next;
            
            if(begin>beginNode->begin){
                Split(beginNode,begin);
            }
    
            endNode = beginNode;
            while(endNode->end < end)
                endNode = endNode->next;
                
            if(end < endNode->end){
                Split(endNode,end);
                if(endNode->last->begin == begin)
                    beginNode = endNode->last;
            }else{
                if(endNode!=tail)
                    endNode = endNode->next;
                else{
                    endNode->next = new Node(end,INT_MAX,0);
                    endNode->next->last = endNode;
                    endNode = endNode->next;
                    tail = endNode;
                }
            }
            
            Node* ptr;
            for(ptr = beginNode;ptr!=endNode;ptr=ptr->next){
                ptr->height = (ptr->height > height)? ptr->height:height;
                Merge(ptr);
                if(ptr->begin<=begin)
                    beginNode = ptr;
            }
            Merge(endNode);
            if(endNode->begin<=begin)
                    beginNode = endNode;
        }
        
        Node* ptr;
        int lastheight=-1;
        for(ptr = head->next;ptr!=NULL;ptr = ptr->next){
            if(ptr->height!=lastheight){
                results.push_back(make_pair(ptr->begin,ptr->height));
                lastheight = ptr->height;
            }
        }
        
        return results;
    }
    

    };
    '''


  • 0
    Q

    Really fast. I tried and it takes only 29 ms and beats 100%. However it is too long.


Log in to reply
 

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