A segment tree solution


  • 3
    C
    class Solution {
    public:
        int tree[20000<<2] = {};
        void update(int n, int l, int r, int left, int right, int value) {
            if(l == left && r == right) {
                tree[n] = max(tree[n], value);
            }
            else {
                int m = (l+r)>>1;
                if(right <= m) {
                    update(n<<1, l, m, left, right, value);
                }
                else if(left > m) {
                    update(n<<1|1, m+1, r, left, right, value);
                }
                else {
                    update(n<<1, l, m, left, m, value);
                    update(n<<1|1, m+1, r, m+1, right, value);
                }
            }
        }
        int query(int n, int l, int r, int index) {
            if(l == r) {
                return tree[n];
            }
            else {
                int m = (l+r) >> 1;
                int res = (index <= m ? query(n<<1, l, m, index) : query(n<<1|1, m+1, r, index));
                return max(res, tree[n]);
            }
        }
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            unordered_map<int, int> line;
            unordered_map<int, int> rline;
            int n = buildings.size();
            set<int> l;
            int top = -2;
            int pre = -1;
            for(int i = 0; i < n; i++) {
                l.insert(buildings[i][0]);
                l.insert(buildings[i][1]);
            }
            set<int>::iterator it;
            for(it = l.begin(); it != l.end(); it++) {
                if(pre != -1 && *it == pre+1) {
                    top++;
                }
                else {
                    top+=2;
                }
                line[*it] = top;
                rline[top] = *it;
                pre = *it;
            }
            for(int i = 0; i < n; i++) {
                update(1, 0, top, line[buildings[i][0]], line[buildings[i][1]], buildings[i][2]);
            }
            vector<pair<int, int>> res;
            int ph = 0;
            for(int i = 0; i <= top; i++) {
                int h = query(1, 0, top, i);
                if(h != ph) {
                    res.push_back(make_pair(h > ph ? rline[i] : rline[i-1], h));
                    ph = h;
                }
            }
            if(n > 0) {
                res.push_back(make_pair((rline[top]), 0));
            }
            return res;
        }
    };

  • 1
    I

    Segment Tree by O(nlg(n)) time, 43 seconds in Java Version.

    All buildings on X-axis construct at most buildings.length intervals, and this is the Segment Tree leaf node.
    Before building this tree, we should also re-number these nodes.

    For each tree node we maintain the max height of its range.

    struct Node {
        int startRange, endRange;
        int maxHeight;
       Node *pleft, *pright;
    }
    

    Notes:

    Here we use lazy propagation to update node. If at some node the range is exactly matched, update this node and don't update its child nodes.

    Videos about segment tree:

    Segment Tree Range Minimum Query

    Lazy Propagation Segment Tree

    class SegTree {
        int[] segTree;  //从node = 1开始有效
    
        public SegTree(int size) {
            segTree = new int[size];
        }
    
        void update(int node, int startRange, int endRange, int left, int right, int value) {
            if (left > right || right < startRange || left > endRange)
                return;
            //类似lazy propagation
            if (startRange == left && endRange == right) {
                segTree[node] = Math.max(segTree[node], value);
                return;
            }
            int mid = (startRange + endRange) >> 1;
            update(node << 1, startRange, mid, left, Math.min(mid, right), value);
            update((node << 1) + 1, mid + 1, endRange, Math.max(mid + 1, left), right, value);
        }
    
        int query(int node, int startRange, int endRange, int index) {
            if (startRange == endRange)
                return segTree[node];
            int mid = (startRange + endRange) >> 1;
            int res = index <= mid ? query(node << 1, startRange, mid, index) : query((node << 1) + 1, mid + 1, endRange, index);
            return Math.max(res, segTree[node]); //do this, because of lazy propagation
        }
    }
    
    public class Solution {
    
        public List<int[]> getSkyline(int[][] buildings) {
            Set<Integer> ts = new TreeSet<>(); //sorted by ascending order
            for (int i = 0; i < buildings.length; i++) {
                ts.add(buildings[i][0]);
                ts.add(buildings[i][3]);
            }
            //将X坐标区间到映射成1,2..连续值区间
            Map<Integer, Integer> map = new HashMap<>(), rMap = new HashMap<>();
            int k = 0;
            for (Integer it : ts) {
                map.put(it, k);
                rMap.put(k++, it);
            }
            k = k - 1;
            SegTree segTree = new SegTree((k + 1) << 4);
            //build segTree
            for (int i = 0; i < buildings.length; i++) {
                segTree.update(1, 0, k, map.get(buildings[i][0]), map.get(buildings[i][4]) - 1, buildings[i][2]);
            }
            int preHeight = 0, height;
            List<int[]> ret = new ArrayList<>();
            for (int i = 0; i <= k; i++) {
                height = segTree.query(1, 0, k, i);  //ith 区间max height
                if (preHeight == height) continue; //连续区间相同高度 取第一个即可
                ret.add(new int[]{rMap.get(i), height});  //转化为实际区间
                preHeight = height;
            }
            return ret;
        }
    }
    

  • 0
    D

    a Typo, second line of ts.add() should be ts.add(buildings[i][1]);


Log in to reply
 

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