力扣（leetcode）每日一题 699 掉落的方块

699. 掉落的方块

题干

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

题解

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

java">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; // 反正不会更新为0List<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 + i2update(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上。非常的紧凑