[LeetCode解题报告] 699. 掉落的方块
[LeetCode解题报告] 699. 掉落的方块
-
- 一、 题目
-
- 1. 题目描述
- 2. 原题链接
- 二、 解题报告
-
- 1. 思路分析
- 2. 复杂度分析
- 3.代码实现
- 三、 本题小结
一、 题目
1. 题目描述
在二维平面上的 x 轴上,放置着一些方块。
给你一个二维整数数组 positions
,其中 positions[i] = [lefti, sideLengthi]
表示:第 i
个方块边长为 sideLengthi
,其左侧边与 x 轴上坐标点 lefti
对齐。
每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向下落,直到着陆到 另一个正方形的顶边 或者是 x 轴上 。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆,它就会固定在原地,无法移动。
在每个方块掉落后,你必须记录目前所有已经落稳的 方块堆叠的最高高度 。
返回一个整数数组 ans
,其中 ans[i]
表示在第 i
块方块掉落后堆叠的最高高度。
示例 1:
输入:positions = [[1,2],[2,3],[6,1]]
输出:[2,5,5]
解释:
第 1 个方块掉落后,最高的堆叠由方块 1 组成,堆叠的最高高度为 2 。
第 2 个方块掉落后,最高的堆叠由方块 1 和 2 组成,堆叠的最高高度为 5 。
第 3 个方块掉落后,最高的堆叠仍然由方块 1 和 2 组成,堆叠的最高高度为 5 。
因此,返回 [2, 5, 5] 作为答案。
示例 2:
输入:positions = [[100,100],[200,100]]
输出:[100,100]
解释:
第 1 个方块掉落后,最高的堆叠由方块 1 组成,堆叠的最高高度为 100 。
第 2 个方块掉落后,最高的堆叠可以由方块 1 组成也可以由方块 2 组成,堆叠的最高高度为 100 。
因此,返回 [100, 100] 作为答案。
注意,方块 2 擦过方块 1 的右侧边,但不会算作在方块 1 上着陆。
提示:
1 <= positions.length <= 1000
1 <= lefti <= 108
1 <= sideLengthi <= 106
Related Topics
- 线段树
- 数组
- 有序集合
- 👍 126
- 👎 0
2. 原题链接
链接: 699. 掉落的方块
二、 解题报告
1. 思路分析
- 每一个方块下落,高度取决于它的底边碰到谁,也就是需求当前底边所在线段[l,r]上的最大高度。
- 容易想到这是线段树的思路,用线段树维护x轴上每块线段上承载的高度,于是:
- 方块落到哪:区间查询[l,r]上的最高高度,求区间极值
- 方块落下后:区间更新[l,r]上维护的高度,区间更新,用lazytag优化
- 每次落下后,线段树根节点储存的就是现在最大高度。
- 由于数据范围大(108),需要散列化。
- 要散列化的值就是x轴上的所有线段端点,即所有方块的left和right
2. 复杂度分析
时间复杂度O(nlog2m),n是正方形个数,m是散列化数组长度,很明显m<=n*2
3.代码实现
线段树
,IUIQ
,区间更新区间查询(求极值)
。
class IntervalTree: def __init__(self, size): self.size = size self.interval_tree = [0 for _ in range(size*4)] self.lazys = [0 for _ in range(size*4)] def give_lay_to_son(self,p,l,r): interval_tree = self.interval_tree lazys = self.lazys if lazys[p] == 0: return mid = (l+r)//2 interval_tree[p*2] = lazys[p] interval_tree[p*2+1] = lazys[p] lazys[p*2] = lazys[p] lazys[p*2+1] = lazys[p] lazys[p] = 0 def update(self,p,l,r,x,y,val): """ 把[x,y]区域全变成val """ interval_tree = self.interval_tree lazys = self.lazys if x <= l and r<=y: interval_tree[p] = val lazys[p] = val return self.give_lay_to_son(p,l,r) mid = (l+r)//2 if x <= mid: self.update(p*2,l,mid,x,y,val) if mid < y: self.update(p*2+1,mid+1,r,x,y,val) interval_tree[p] = max(interval_tree[p*2], interval_tree[p*2+1]) def query(self,p,l,r,x,y): """ 查找x,y区间的最大值 """ if x<=l and r<=y: return self.interval_tree[p] self.give_lay_to_son(p,l,r) mid = (l+r)//2 s = 0 if x <= mid: s = max(s,self.query(p*2,l,mid,x,y)) if mid < y: s = max(s,self.query(p*2+1,mid+1,r,x,y)) return sclass Solution: def fallingSquares(self, positions: List[List[int]]) -> List[int]: n = len(positions) hashes = [left for left,_ in positions] + [left+side for left,side in positions] hashes = sorted(list(set(hashes))) # 用线段树维护x轴区间最大值,记录每个点的高度:比如[1,2]这个方块,会使线段[1,2]闭区间这个线段上的每个高度都变成2 # 落下一个新方块时,查询它的底边所在线段[x,y]的最大高度h,这个方块会落在这个高度h,把新高度h+side插入线段树[x,y]的部分 # 每次插入结束,树根存的高度就是当前最大高度 # 由于数据范围大1 <= lefti <= 108,需要散列化 # 散列化的值有left和right(线段短点) # print(hashes) tree_size = len(hashes) tree = IntervalTree(tree_size) heights = [] for left,d in positions: right = left + d l = bisect_left(hashes,left) r = bisect_left(hashes,right) h = tree.query(1,1,tree_size,l+1,r) tree.update(1,1,tree_size,l+1,r,h+d) heights.append(tree.interval_tree[1]) return heights
三、 本题小结
- 遇到问题先想想暴力怎么解,然后再优化
- 本题暴力解法是:对每个方块,遍历它前边所有方块的落下后的顶边高度,如果重叠,则自己的高度可求,复杂度O(n2)