Leetcode每日一题 —— 3454. 分割正方形 II

Leetcode每日一题：分割正方形 II

题目链接：分割正方形 II

思路：
今天我们讨论的是Leetcode上的题目——分割正方形 II。与昨天的题目类似，但有所不同。关键点在于重叠面积只计算一次，因此每个高度不能直接累加宽度计算面积，而是要通过线段组合计算。因此，每个高度需要先计算一次有效宽度。

我的思路是将所有线段都放到一个List中，通过引用快速移除顶部的线段，然后根据x值排序后累加计算有效宽度。获取有效宽度后，就跟昨天的题目一样处理了。

代码：

    /**
     * 计算当前有效宽度
     * @param segList 此前包含的线段
     * @param addList 当前高度调整的线段
     * @return 有效宽度
     */
    private int combineLine(List<int> segList, List<int> addList) {
        // 遍历调整的线段，如果没有添加过(底边)则将第三个数置为1，否则(顶边)移除
        for (int add : addList) {
            if (add[2] == 1) {
                segList.remove(add);
            } else {
                add[2] = 1;
                segList.add(add);
            }
        }
        // 按照x轴排序，方便统计长度，宽度排不排序均可
        segList.sort((a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);

        // 从左到右统计有效宽度，重叠部分不计
        int totalLen = 0;
        int loc = Integer.MIN_VALUE;
        for (int segment : segList) {
            if (segment[1] == 0) continue;
            int currentStart = segment[0];
            int currentEnd = segment[0] + segment[1];
            if (currentStart > loc) {
                totalLen += segment[1];
                loc = currentEnd;
            } else if (currentEnd > loc) {
                totalLen += currentEnd - loc;
                loc = currentEnd;
            }
        }

        return totalLen;
    }

    /**
     * 3454. 分割正方形 II
     * 与昨天不同的是，重叠面积只算一次，因此每个高度不能直接累加宽度计算面积，要通过线段组合计算。因此每个高度需要先计算一次有效宽度。
     * 我的思路是将所有线段都放到一个List中，通过引用快速移除顶的线段，然后根据x值排序后累加计算有效宽度。
     * @param squares 正方形的信息
     * @return 分割的高度
     * @link <a href="https://leetcode.cn/problems/separate-squares-ii">3454. 分割正方形 II</a>
     */
    public double separateSquares(int squares) {
        // 边记录，记录当前高度包含的块的 边-线段 键值对。底边增加一份引用，顶边再次增加**同一份引用**用于移除。
        TreeMap<Integer, List<int>> top = new TreeMap<>();
        for (int square : squares) {
            // 创建线段，将底边和顶边的引用分别添加到map中，第三个数用于判断是底还是顶
            int tmp = new int { square[0], square[2], 0 };
            top.compute(square[1], (k, v) -> {
                if (v == null) {
                    v = new ArrayList<>();
                }
                v.add(tmp);
                return v;
            });
            top.compute(square[1] + square[2], (k, v) -> {
                if (v == null) {
                    v = new ArrayList<>();
                }
                v.add(tmp);
                return v;
            });
        }
        int y = Integer.MIN_VALUE;
        int w = 0;
        double totalArea = 0;
        List<int> line = new LinkedList<>();
        TreeMap<Integer, Integer> map = new TreeMap<>();
        // 从下往上遍历每条边，计算当前有效宽度，并以此计算总面积
        while (!top.isEmpty()) {
            Map.Entry<Integer, List<int>> entry = top.pollFirstEntry();
            int cy = entry.getKey();
            int cw = combineLine(line, entry.getValue());
            map.put(cy, cw);
            totalArea += (double) w * (cy - y);
            y = cy;
            w = cw;
        }
        y = Integer.MIN_VALUE;
        w = 0;
        double half = totalArea / 2;
        // 从下往上遍历每条边，并计算面积，如果面积超过了一半，则通过面积计算高度并返回结果。
        while (!map.isEmpty()) {
            Map.Entry<Integer, Integer> entry = map.pollFirstEntry();
            int cy = entry.getKey();
            int cw = entry.getValue();
            if (w > 0) {
                double area = (double) (cy - y) * w;
                if (half <= area) {
                    return half / w + y;
                }
                half -= area;
            }
            y = cy;
            w = cw;
        }
        return -1;
    }

PS：
看了下更快的方法，使用的是线段树结构，容我先学习一下。