C++ 100% (29~36ms) solution: help me beaufity the ugly code


  • 0

    My strategy is to maintain the contour in a std::list. and for each building I do the following steps:

    1. At first in the loop body, look for the insertion point.
    2. Check if we need to insert a new point for left value, or adjust height when l is the same as certain vertical line in the current contour.
    3. Check if any dominated point to remove.

    The code:

    #define X first
    #define Y second
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            list<pair<int,int>> contour;
            auto it = contour.end();
            auto it2 = it;
            
            for(const auto& v : buildings) {
                int l = v[0], r = v[1], h = v[2];
                
                while(it != contour.end() && it->X < l) ++it;
                if(it == contour.end()) {
                    it = contour.insert(it,make_pair(l,h));
                    contour.push_back(make_pair(r,0));
                    continue;
                }
                if(it->X > l) --it;
                int prevH = it->Y;
                if(it->Y < h) {
                    if(it->X < l) it = contour.insert(++it, make_pair(l,h));
                    else {
                        if(it != contour.begin()) {
                            it2 = it, --it2;
                            if(it2->Y != h) it->Y = h;
                            else contour.erase(it), it = it2;
                        } else it->Y = h;
                    }
                    it2 = it, ++it2;
                }
                else {
                    it2 = it;
                    while(it2->X < r && it2->Y > h) ++it2;
                    if(it2->X >= r) continue;
                    prevH = it2->Y;
                    it2->Y = h;
                    ++it2;
                }
                while(it2!=contour.end() && it2->X < r) prevH = it2->Y, it2 = contour.erase(it2);
                if(contour.end() == it2 || it2->X != r) contour.insert(it2,make_pair(r,prevH));
            }
            return vector<pair<int,int>>(contour.begin(),contour.end());
        }
    

    I think I will save time on explaining the code because there are quite a few corner cases handled in the code, and you will know what the code trying to do if you worked this problem before. The key to this algorithm is to maintain 'prevH' for potential insertion at the end of loop body. If anyone is interested, focus on this variable; others are just tedious work.

    Using std::list result in needs of many operations on iterator, like moving back or forth, which makes the code a little bit complicated, but actually the idea is really simple.

    Anyone can give suggestion?


Log in to reply
 

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