699.掉落的方块

链接：699.掉落的方块
难度：Hard
标签：线段树、数组、有序集合
简介：在每个方块掉落后，你必须记录目前所有已经落稳的 方块堆叠的最高高度 。返回一个整数数组 ans ，其中 ans[i] 表示在第 i 块方块掉落后堆叠的最高高度。

题解 1 - python

• 编辑时间：2024-07-28
• 执行用时：407ms
• 内存消耗：16.72MB
• 编程语言：python
• 解法介绍：枚举每一个块与另一个块是否位置产生交集。

class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        n = len(positions)
        harr = [0] * n
        maxh = 0
        res = []
        for i in range(n):
            l1, h1 = positions[i]
            harr[i] = h1
            for j in range(i):
                l2, h2 = positions[j]
                if l1 + h1 - 1 >= l2 and l2 + h2 - 1 >= l1:
                    harr[i] = max(harr[i], harr[j] + h1)
            maxh = max(maxh, harr[i])
            res.append(maxh)
        return res