掉落的方块

标签: 线段树 数组 有序集合

难度: Hard

在二维平面上的 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

Submission

运行时间: 63 ms

内存: 16.8 MB

class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        arr = [(p, i, 0) for i, (p, _) in enumerate(positions)]
        for i in range(len(positions)):
            arr.append((sum(positions[i]), i, 1))
        arr.sort()
        intervals = [[-1, -1, 0] for _ in range(len(positions))]
        pre = -1
        j = -1
        for p, i, l in arr:
            if p != pre:
                j += 1
            intervals[i][l] = j
            if l == 1:
                intervals[i][-1] = positions[i][-1]
            pre = p
        x = [0] * (2 * len(intervals))
        ans = []
        ma = 0
        for l, r, h in intervals:
            h += max(x[l:r])
            for i in range(l, r):
                x[i] = h
            ma = max(h, ma)
            ans.append(ma)
        return ans

Explain

这个题解的思路是：首先将每个方块的左右坐标和高度信息存储在一个数组 arr 中，并按照坐标大小排序。然后遍历 arr，对于每个方块，记录其在 x 轴上的区间范围 [l, r]，以及该区间内方块的最大高度。最后遍历每个区间，更新该区间内的最大高度，并记录当前的最大高度到答案数组中。

时间复杂度: O(nlogn)

空间复杂度: O(n)

class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        # 将每个方块的左右坐标和高度信息存储在 arr 中
        arr = [(p, i, 0) for i, (p, _) in enumerate(positions)]
        for i in range(len(positions)):
            arr.append((sum(positions[i]), i, 1))
        # 按照坐标大小排序
        arr.sort()
        
        # 存储每个方块的区间信息 [l, r, h]
        intervals = [[-1, -1, 0] for _ in range(len(positions))]
        pre = -1
        j = -1
        for p, i, l in arr:
            if p != pre:
                j += 1
            intervals[i][l] = j
            if l == 1:
                intervals[i][-1] = positions[i][-1]
            pre = p
        
        # 存储每个位置的最大高度
        x = [0] * (2 * len(intervals))
        ans = []
        ma = 0
        for l, r, h in intervals:
            # 更新区间 [l, r] 内的最大高度
            h += max(x[l:r])
            for i in range(l, r):
                x[i] = h
            ma = max(h, ma)
            ans.append(ma)
        return ans

Explore

在arr数组中，除了存储坐标点外，还包含了一个标识符i，这个标识符i是方块的索引，它用于标记每个坐标点属于哪一个方块。在对arr数组进行排序后，通过这个标识符i可以确保即使坐标位置发生了变化，依然可以准确地将每个坐标点关联回原来的方块。这样，我们就可以通过索引i来追踪和更新每个方块的左右边界。

单独存储每个方块的区间信息在intervals数组中是为了方便处理和更新方块的高度信息。在处理方块落下的模拟中，需要频繁地查询和更新每个方块的高度，特别是当新的方块落在已有的方块堆叠上时。通过预先存储每个方块的区间[l, r]，可以快速定位到受影响的区间并进行高度的更新。这种设计使得代码逻辑更清晰，且能更高效地处理方块的堆叠与更新操作。

题解中的`h += max(x[l:r])`逻辑是用来计算当前方块堆叠在之前方块上的最终高度。这里`max(x[l:r])`表示在当前方块的水平区间[l, r]内，已经存在的方块的最大高度。将当前方块的高度h加上这个最大值，就得到了当前方块落在最高堆叠上的总高度。这是实现方块按顺序堆叠，并正确计算每次方块落下后的最高点的关键步骤。

尽管理论上可以尝试合并两次遍历的步骤以简化代码和可能的性能提升，但在实际操作中，合并这两步可能会导致逻辑复杂度增加，因为更新最大高度依赖于完整的区间信息。在第一次遍历中，我们建立了方块的区间映射，这为第二次遍历提供了必要的前置信息。如果合并这两个步骤，可能需要在遍历过程中动态地调整和计算区间信息，这可能增加错误发生的概率并降低代码的可读性。因此，尽管两步遍历看似冗余，却能保证逻辑的清晰和数据操作的正确性。