本文共 3065 字，大约阅读时间需要 10 分钟。

package com.chanmufeng.questions;import java.util.*;public class Skyline {    public static class Node {        public int pos;        public int height;        public boolean isUp;        public Node(int pos, int height, boolean isUp) {            this.pos = pos;            this.height = height;            this.isUp = isUp;        }        @Override        public String toString() {            return "[" + pos + " " + height + " " + isUp + "]";        }    }    public static class NodeComparator implements Comparator
   
     {        @Override        public int compare(Node o1, Node o2) {            //如果位置不相等，将位置升序            if (o1.pos != o2.pos) {                return o1.pos - o2.pos;            }            //如果位置相等，优先排列下降的位置            if (o1.isUp != o2.isUp) {                return o1.isUp ? 1 : -1;            }            return 0;        }    }    public static List
    
      getSkyline(int[][] buildings) {        Node[] nodes = new Node[buildings.length * 2];        int index = 0;        for (int i = 0; i < buildings.length; i++) {            nodes[index++] = new Node(buildings[i][0], buildings[i][2], true);            nodes[index++] = new Node(buildings[i][1], buildings[i][2], false);        }        Arrays.sort(nodes, new NodeComparator());        //key：高度 value：高度出现的次数        TreeMap
     
       htMap = new TreeMap<>();        //key:position value:该位置的最高高度        TreeMap
      
        pmMap = new TreeMap<>();        List
       
         res = new LinkedList<>();        for (int i = 0; i < nodes.length; i++) {            if (nodes[i].isUp) {                if (!htMap.containsKey(nodes[i].height)) {                    htMap.put(nodes[i].height, 1);                } else {                    htMap.put(nodes[i].height, htMap.get(nodes[i].height) + 1);                }            } else {                if (htMap.get(nodes[i].height) == 1) {                    htMap.remove(nodes[i].height);                } else {                    htMap.put(nodes[i].height, htMap.get(nodes[i].height) - 1);                }            }            if (htMap.isEmpty()) {                pmMap.put(nodes[i].pos, 0);            } else {                pmMap.put(nodes[i].pos, htMap.lastKey());            }        }        int height = 0;        Iterator it = pmMap.entrySet().iterator();        while (it.hasNext()) {            Map.Entry entry = (Map.Entry) it.next();            int curMaxHeight = (int) entry.getValue();            if (height != curMaxHeight) {                int[] temp = new int[2];                temp[0] = (int) entry.getKey();                temp[1] = curMaxHeight;                ((LinkedList
        
         ) res).addLast(temp); height = curMaxHeight; } } return res; } public static void main(String[] args) { int[][] arr = { {2, 9, 10}, {3, 7, 15}, {5, 12, 12}, {15, 20, 10}, {19, 24, 8}, };// int[][] arr = {// {1, 3, 3},// {2, 4, 2},// {4, 5, 1},// }; List res = getSkyline(arr); for (int i = 0; i < res.size(); i++) { for (int item : (int[]) res.get(i)) { System.out.print(item + " "); } System.out.println(); } }}
        
       
      
     
    
   

转载地址：http://ksaxb.baihongyu.com/