力扣（leetcode）每日一题 699 掉落的方块 | 线段树|经典

699. 掉落的方块

题干

在二维平面上的 x 轴上，放置着一些方块。
给你一个二维整数数组 positions ，其中 positions[i] = [lefti, sideLengthi] 表示：第 i 个方块边长为 sideLengthi ，其左侧边与 x 轴上坐标点 lefti 对齐。
每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向下落，直到着陆到 另一个正方形的顶边 或者是 x 轴上 。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆，它就会固定在原地，无法移动。
在每个方块掉落后，你必须记录目前所有已经落稳的 方块堆叠的最高高度 。
返回一个整数数组 ans ，其中 ans[i] 表示在第 i 块方块掉落后堆叠的最高高度。

题解

这个题目不仅需要用线段树，在进行线段树初始化的时候还有一个非常重要的技巧

class Solution {

    public static List<Integer> fallingSquares(int[][] positions) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (int[] position : positions) {
            treeSet.add(position[0]);
            treeSet.add(position[0] + position[1] - 1);
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 1;
        for (Integer i : treeSet) {
            map.put(i, count);
            count++;
        }
        SegmentTree segmentTree = new SegmentTree(map.size());
        segmentTree.build(positions, map);
        return segmentTree.getResult();

    }

    // 位置1 位置2   遍历位置  数量累加？

    public static class SegmentTree {
        int root = 1;
        int left = 1;
        int right;
        int[] maxArr;
        int[] updateArr; // 反正不会更新为0
        List<Integer> collect = new ArrayList<>();

        public SegmentTree(int n) {
            int length = n + 1;
            right = n;
            maxArr = new int[length * 4];
            updateArr = new int[length * 4];
        }

        public void update(int start, int end, int value) {
            update(start, end, value, left, right, root);
        }

        public void update(int start, int end, int value, int left, int right, int node) {
            if (start <= left && right <= end) {
                updateArr[node] = value;
                maxArr[node] = value;
                return;
            }
            int mid = (left + right) / 2;
            if (start <= mid) {
                update(start, end, value, left, mid, node * 2);
            }
            if (mid < end) {
                update(start, end, value, mid + 1, right, node * 2 + 1);
            }
            maxArr[node] = Math.max(maxArr[node * 2], maxArr[node * 2 + 1]);
        }

        public int getMax(int start, int end) {
            return getMax(start, end, left, right, root);
        }

        public int getMax(int start, int end, int left, int right, int node) {
            if (start <= left && right <= end) {
                return maxArr[node];
            }
            int mid = (left + right) / 2;
            int max = 0;
            int max2 = 0;
            // 刷新
            if (updateArr[node] != 0) {// 下发任务
                updateArr[node * 2] = updateArr[node];
                updateArr[node * 2 + 1] = updateArr[node];
                maxArr[node * 2] = updateArr[node];
                maxArr[node * 2 + 1] = updateArr[node];
                updateArr[node] = 0;
            }
            if (start <= mid) {
                max = getMax(start, end, left, mid, node * 2);
            }
            if (mid < end) {
                max2 = getMax(start, end, mid + 1, right, node * 2 + 1);
            }
            return Math.max(max, max2);
        }

        int curMax = 0;

        public void build(int[][] positions, HashMap<Integer, Integer> map) {
            for (int[] position : positions) {
                int i1 = position[0]; // 2，2      2，3 算头不算尾
                int i2 = position[1];
                Integer index1 = map.get(i1);
                Integer index2 = map.get(i1 + i2 - 1);
                // 获取范围上的最大值
                int max = getMax(index1, index2); // 范围 i1, i1 + i2
                update(index1, index2, max + i2);
                curMax = Math.max(curMax, max + i2);
                collect.add(curMax);
            }
        }

        public List<Integer> getResult() {
            return collect;
        }
    }

}

总结

还是去网上找视频看把，这个真不好解释

首先正放心 4，6 会落在4，6和10，6的位置，但是10，6的位置是没有支点的，也就是用不了的。因为这时候10位置来了方块，是无法累加上去的
然后这里不能记录4,6 5,6 6,6 7,6 8,6 9,6 这里需要对点进行map的压缩。
这样只要头尾的点就可以了。
也就是你会有很多点 数值很大 100,10000,555555,666666,666669
但是会通过hash映射到 1，2，3，4，5上。非常的紧凑