1.题目基本信息

1.1.题目描述

在二维平面上的 x 轴上，放置着一些方块。

给你一个二维整数数组 positions ，其中 positions[i] = [lefti, sideLengthi] 表示：第 i 个方块边长为 sideLengthi ，其左侧边与 x 轴上坐标点 lefti 对齐。

每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向下落，直到着陆到 另一个正方形的顶边 或者是 x 轴上 。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆，它就会固定在原地，无法移动。

在每个方块掉落后，你必须记录目前所有已经落稳的 方块堆叠的最高高度 。

返回一个整数数组 ans ，其中 ans[i] 表示在第 i 块方块掉落后堆叠的最高高度。

1.2.题目地址

https://leetcode.cn/problems/falling-squares/description/

2.解题方法

2.1.解题思路

线段树。维护各个区间的最大值，由于数字的范围很大，所以采用动态修改的线段树

3.解题代码

python3代码

class SegNode:
    def __init__(self, l:int, r:int):
        # > 维护左右结点的指针
        self.left = None
        self.right = None
        # > 维护结点对应区间的左右端点，这里也维护一下区间的中间位置
        self.l = l
        self.r = r
        self.mid = (r - l) // 2 + l
        # > value维护当前区间的最大值；lazy维护是否当前结点是否执行过懒操作，即子孙节点更新被记录还没有执行
        self.value = -inf
        self.lazy = False

class SegmentTree:
    def __init__(self, n:int):
        self.root = SegNode(0, n)
    
    # 更新区间[start,end]的值为value
    def rangeUpdate(self, start:int, end:int, value:int):
        return self._rangeUpdate(start, end, value, self.root)
    
    # 查询区间[start,end]中的最大值
    def rangeMax(self, start:int, end:int) -> int:
        return self._rangeMax(start, end, self.root)
    
    # > 更新node结点区间和[start,end]区间的交集的值为value
    def _rangeUpdate(self, start:int, end:int, value:int, node:SegNode):
        # 第一步，如果区间交集为空，则无需更新，直接返回
        if start > end:
            return
        if start > node.r or end < node.l:
            return
        # 第二步，如果结点node结点完全在[start,end]区间中，则直接更新node并返回
        if node.l >= start and node.r <= end:
            node.value = value
            node.lazy = True
            return
        # 第三步，如果区间交集不为空，且node区间没有被包含，则在将node结点pushdown后，递归更新左右结点，并在更新左右结点后，pushup根据子节点更新node节点（这里由于是外部调用都是从root开始，所以可以保证所有相关的结点都通过pushup进行更新）
        self.pushdown(node)
        if start <= node.mid:
            # 注意：这里的递归的范围必须用[start,end]，因为end可能小于node.mid
            self._rangeUpdate(start, end, value, node.left)
        if end > node.mid:
            self._rangeUpdate(start, end, value, node.right)
        self.pushup(node)

    # > 获取node结点区间和[start,end]区间的交集区间中的最大值
    def _rangeMax(self, start:int, end:int, node:SegNode) -> int:
        # 第一步，如果区间交集为空，这里不存在需要找的最大值，直接返回-inf
        if start > end:
            return -inf
        if start > node.r or end < node.l:
            return -inf
        # 第二步，如果结点node结点完全在[start,end]区间中，则直接返回node的值
        if node.l >= start and node.r <= end:
            return node.value
        # 第三步，如果区间交集不为空，且node区间没有被包含，则在将node结点pushdown后，递归查询左右结点区间的最大值
        self.pushdown(node)
        ans = -inf
        if start <= node.mid:
            # 注意：这里的递归的范围必须用[start,end]，因为end可能小于node.mid
            ans = max(ans, self._rangeMax(start, end, node.left))
        if end > node.mid:
            ans = max(ans, self._rangeMax(start, end, node.right))
        return ans
    
    # > 根据子节点的值更新node结点的值
    def pushup(self, node:SegNode = None):
        node.value = max(node.left.value, node.right.value)
    
    # > 将node的懒操作部分下沉到子节点
    def pushdown(self, node:SegNode = None):
        if node.left is None:
            node.left = SegNode(node.l, node.mid)
        if node.right is None:
            node.right = SegNode(node.mid + 1, node.r)
        if node.lazy:
            node.left.value = node.value
            node.right.value = node.value
            node.left.lazy = True
            node.right.lazy = True
            node.lazy = False


class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        # 思路：线段树。维护各个区间的最大值，由于数字的范围很大，所以采用动态修改的线段树
        segTree = SegmentTree(1e9)
        result = [0] * len(positions)
        maxVal = 0
        for i, (left, edge) in enumerate(positions):
            maxH = max(segTree.rangeMax(left, left + edge - 1), 0)
            segTree.rangeUpdate(left, left + edge - 1, maxH + edge)
            maxVal = max(maxVal, maxH + edge)
            result[i] = maxVal
        return result

4.执行结果