C++ solution using map and unordered_set, easy to understand


  • 0
    M

    My method use two maps to store information. The first map, called pos2Heights, maps a position on x-axis to an unordered set containing all the building heights at this position. Note for right edges, the corresponding building heights have a minus sign. For example, for a input like [[1, 4, 1], [2, 3, 2], [3, 4, 3]], pos2Heights should look like:
    1 --> {1}
    2 --> {2}
    3 --> {-2, 3}
    4 --> {-1, -3}.
    The second map, called heightCount, is used during the iteration of pos2Heights and records the count of each height value. Therefore, for each position x, the maximum height of heightCount after visiting the set pos2Heights[x] can reflect the height of skyline at x.

    class Solution {
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            int n = buildings.size();
            vector<pair<int, int>> res;
            
            map<int, unordered_set<int>> pos2Heights;
    
            for (auto& building : buildings)
            {
                int leftEdgePos = building[0], rightEdgePos = building[1];
                int height = building[2];
                
                pos2Heights[leftEdgePos].insert(height);
                pos2Heights[rightEdgePos].insert(-height);
            }
            
            map<int, int> heightCount;
            int maxHeightOld = INT_MIN;
            
            for (auto& iter : pos2Heights)
            {
                int position = iter.first;
                
                for (auto height : iter.second)
                {
                    //left edge at this position: add height to heightCount
                    if (height > 0) 
                        heightCount[height]++;
                    //right edge: remove height from heightCount
                    else 
                    {
                        height = -height;
                        heightCount[height]--;
                        if (heightCount[height] == 0)
                            heightCount.erase(height);
                    }
                }
                
                // get the maximum height in heightCount
                int maxHeight = 0;
                if (!heightCount.empty())
                    maxHeight = (*(heightCount.rbegin())).first;
                
                if (maxHeight != maxHeightOld)
                    res.push_back(make_pair(position, maxHeight));
                    
                maxHeightOld = maxHeight;
            }
            
            return res;
        }
    };
    

Log in to reply
 

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