Java中的SkylineProblem

Question

摘自leetcode.com:

从远处看，城市的天际线是由城市内所有建筑物形成的轮廓的外部轮廓。鉴于所有建筑物的位置和高度，返回由这些建筑物共同形成的天际线。...

请检查这段代码。我最感兴趣的是关于OOP原理的反馈(坚实、可读性等)。其次是对表演最感兴趣。

类解决方案

public class Solution {

    public static void main(String[] args) {
        final int[][] input = {{2,9,10},{3,7,15},{5,12,12},{15,20,10},{19,24,8}};
        Solution solution = new Solution();
        System.out.println("amount : "+solution.getSkyline(input));
    }

    //this crude method is a HARD REQUIREMENT and may not be changed!
    public List<List<Integer>> getSkyline(int[][] buildings) {
        SkyLineConverter skyLineConverter = new SkyLineConverter();
        SkyLine skyLine = skyLineConverter.convert(buildings);
        Set<Edge> edges = skyLine.getEdges();
        return sortList(edges);
    }

    private List<List<Integer>> sortList(Set<Edge> edges) {
        List<List<Integer>> result = new ArrayList<>();
        List<Edge> list = new ArrayList<>(edges);
        list.sort(Comparator.comparingInt(o -> o.x));
        for(Edge edge: list){
            List<Integer> intList = new ArrayList<>();
            intList.add(edge.x);
            intList.add(edge.height);
            result.add(intList);
        }
        return result;
    }
}

类SkyLineConverter

public class SkyLineConverter {
    public SkyLine convert(int[][] raw) {
        BuildingConverter buildingConverter = new BuildingConverter();
        List<Building> buildings = buildingConverter.convert(raw);
        return new SkyLine(buildings);
    }
}

类建筑

public class Building {

    public final int x;
    public final int width;
    public final int height;

    public Building(int x, int width, int height) {
        this.x = x;
        this.width = width;
        this.height = height;
    }

}

类BuildingConverter

public class BuildingConverter {

    private static final int FROM_INDEX = 0;
    private static final int TO_INDEX = 1;
    private static final int HEIGHT_INDEX = 2;

    public List<Building> convert(int[][] raw) {
        List<Building> buildings = new ArrayList<>();
        for (int[] buildingRaw: raw){
            int x = buildingRaw[FROM_INDEX];
            int width = buildingRaw[TO_INDEX] - buildingRaw[FROM_INDEX];
            int height = buildingRaw[HEIGHT_INDEX];
            buildings.add(new Building(x,width,height));
        }
        return buildings;
    }
}

类天际线

public class SkyLine {

    private final int width;
    private final Set<Edge> edges = new HashSet<>();
    private final List<Building> buildings;

    public SkyLine(List<Building> buildings) {
        this.buildings = buildings;
        Building mostRight = findMostRight(buildings);
        width = mostRight.x + mostRight.width;
        addEdge();
    }

    private void addEdge() {
        buildings.forEach(b -> {
            addEdge(b.x);
            addEdge(b.x + b.width);
        });
        edges.add(new Edge(width, 0));
    }

    private void addEdge(int x) {
        int skyline = getSkyLine(x);
        int previous = x == 0 ? 0 : getSkyLine(x - 1);
        if (previous < skyline || previous > skyline) {
            edges.add(new Edge(x, skyline));
        }
    }

    private int getSkyLine(int x) {
        List<Building> aroundThisPoint = buildings.stream().
                filter(b -> b.x <= x && b.x + b.width > x).
                collect(Collectors.toList());
        return aroundThisPoint.stream().mapToInt(b -> b.height).max().orElse(0);
    }

    private Building findMostRight(List<Building> buildings) {
        Optional<Building> mostRight = buildings.stream().reduce((a, b) ->
                a.x > b.x ? a : b);
        //noinspection OptionalGetWithoutIsPresent
        return mostRight.get();
    }

    public Set<Edge> getEdges() {
        return edges;

    }

}

类边缘

public class Edge {

    public final int x;
    public final int height;

    public Edge(int x, int height){
        this.x = x;
        this.height = height;
    }

}

Answer 1

我注意到您在大部分代码中都使用了流库，所以我考虑在可能的情况下使用更少的代码行来提高可读性，因为在我看来其他部分都很好。在您的Solution类中，您有以下方法：

private List<List<Integer>> sortList(Set<Edge> edges) {
    List<List<Integer>> result = new ArrayList<>();
    List<Edge> list = new ArrayList<>(edges);
    list.sort(Comparator.comparingInt(o -> o.x));
    for(Edge edge: list){
       List<Integer> intList = new ArrayList<>();
       intList.add(edge.x);
       intList.add(edge.height);
       result.add(intList);
    }
    return result;
}

您可以将edges集与Stream#sorted和Stream#map组合起来直接迭代，从而避免了显式实例化列表的需要，如下所示：

private List<List<Integer>> sortList(Set<Edge> edges) {
        
   return edges.stream()
           .sorted(Comparator.comparingInt(edge -> edge.x))
           .map(edge -> List.of(edge.x, edge.height))
           .collect(Collectors.toList());        
}

在您的BuildingConverter类中，您有以下方法：

public List<Building> convert(int[][] raw) {
    List<Building> buildings = new ArrayList<>();
    for (int[] buildingRaw: raw){
        int x = buildingRaw[FROM_INDEX];
        int width = buildingRaw[TO_INDEX] - buildingRaw[FROM_INDEX];
        int height = buildingRaw[HEIGHT_INDEX];
        buildings.add(new Building(x,width,height));
    }
    return buildings;
}

您的int[][] raw 2d数组的每一行都有可能流到Arrays#stream和Stream#map，以获得相同的预期结果如下所示：

public List<Building> convert(int[][] raw) {

    return Arrays.stream(raw)
           .map(arr -> new Building(arr[FROM_INDEX], 
                                    arr[TO_INDEX] - arr[FROM_INDEX], 
                                    arr[HEIGHT_INDEX]))
           .collect(Collectors.toList());
}

在类SkyLine中，可以简化以下两个方法：

private int getSkyLine(int x) {
    List<Building> aroundThisPoint = buildings.stream().
           filter(b -> b.x <= x && b.x + b.width > x).
           collect(Collectors.toList());
    return aroundThisPoint.stream().mapToInt(b -> b.height).max().orElse(0);
}

private Building findMostRight(List<Building> buildings) {
    Optional<Building> mostRight = buildings.stream().reduce((a, b) ->
           a.x > b.x ? a : b);
    //noinspection OptionalGetWithoutIsPresent
    return mostRight.get();
}

在您的getSkyLine方法中，不需要实例化将要流的中间列表，您可以使用更简洁的方法组合代码行：

private int getSkyLine(int x) {
        
    return buildings.stream()
            .filter(b -> b.x <= x && b.x + b.width > x)
            .mapToInt(b -> b.height)
            .max()
            .orElse(0);
}

findMostRight方法可以使用Collections#max进行简化，如下所示：

private Building findMostRight(List<Building> buildings) {

    return Collections.max(buildings, Comparator.comparingInt(b -> b.x));
}