力扣（leetcode）每日一题 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上。非常的紧凑
原文地址：https://blog.csdn.net/ganjiee0007/article/details/142666057
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！