LeetCode 699. 掉落的方块（碰撞计算 + 逐个遍历）

example.png

暴力来一把，居然过了。

class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        # 感觉像是碰撞检测？

        # 题目理解：
        # 1、x轴上面放立体的方块
        # 2、方块由二维数组表示，[left_i, sideLength_i]，left_i代表方块的左边界位置，sideLength_i代表方块边长度
        # 3、方块往下落，判断能不能落在目前方块的上面

        # 目的：搜索出在哪些方块着陆，获得其中最高方块的高度，计算本方块的高度

        def checkLoad(p1, p2):
            # x轴上面有交集则算着陆
            p1_l = p1[0]
            p1_r = p1[0] + p1[1]

            p2_l = p2[0]
            p2_r = p2[0] + p2[1]

            #3种情况
            if p1_l >= p2_r or p1_r <= p2_l:
                return False
            else:
                return True

        p_nums = len(positions)
        res = []
        all_heights = []
        for i in range(p_nums):
            if i == 0:
                all_heights.append(positions[0][1])
                res.append(positions[0][1])
            else:
                this_max_height = 0
                now_point = positions[i]
                # 此处搜索可以修改为二分搜索
                # 二叉树搜索？
                for j in range(i):
                    if checkLoad(now_point, positions[j]):
                        this_max_height = max(this_max_height, all_heights[j] + now_point[1])

                if this_max_height == 0:
                    this_max_height = now_point[1]

                all_heights.append(this_max_height)
                res.append(max(this_max_height, res[-1]))

        return res