Interview AiBox logo
Interview AiBox
#699
Hard
auto_awesome数组·结合·segment·树

LeetCode 题解工作台

掉落的方块

在二维平面上的 x 轴上，放置着一些方块。 给你一个二维整数数组 positions ，其中 positions[i] = [left i , sideLength i ] 表示：第 i 个方块边长为 sideLength i ，其左侧边与 x 轴上坐标点 left i 对齐。 每个方块都从一个比目…

数组线段树有序集合
category

3

题型

code_blocks

5

代码语言

hub

3

相关题

play_arrow开始看题解arrow_forward
speed复杂度open_in_newLeetCode

当前训练重点

困难 · 数组·结合·segment·树

bolt

答案摘要

根据题目描述，我们需要维护一个区间集合，支持区间的修改和查询操作。这种情况下，我们可以使用线段树来解决。 线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 ，其中 是区间的长度。更新某个元素的值，只需要更新 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用懒标记保证效率。

Interview AiBox logo

Interview AiBox 实时 AI 助手，陪你讲清 数组·结合·segment·树 题型思路

试试 AiBox 面试助手arrow_forward
description

题目描述

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

解题思路

方法一：线段树

根据题目描述，我们需要维护一个区间集合，支持区间的修改和查询操作。这种情况下，我们可以使用线段树来解决。

线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 log⁡(width)\log(width)，其中 widthwidth 是区间的长度。更新某个元素的值，只需要更新 log⁡(width)\log(width) 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用懒标记保证效率。

  • 线段树的每个节点代表一个区间；
  • 线段树具有唯一的根节点，代表的区间是整个统计范围，如 [1,n][1, n]；
  • 线段树的每个叶子节点代表一个长度为 1 的元区间 [x,x][x, x]；
  • 对于每个内部节点 [l,r][l, r]，它的左儿子是 [l,mid][l, mid]，右儿子是 [mid+1,r][mid + 1, r], 其中 mid=l+r2\textit{mid} = \frac{l + r}{2}；

对于本题，线段树节点维护的信息有：

  1. 区间中方块的最大高度 vv
  2. 懒标记 addadd

另外，由于数轴范围很大，达到 10810^8，因此我们采用动态开点。

时间复杂度方面，每次查询和修改的时间复杂度为 O(log⁡n)O(\log n)，总时间复杂度为 O(nlog⁡n)O(n \log n)。空间复杂度为 O(n)O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Node:
    def __init__(self, l, r):
        self.left = None
        self.right = None
        self.l = l
        self.r = r
        self.mid = (l + r) >> 1
        self.v = 0
        self.add = 0


class SegmentTree:
    def __init__(self):
        self.root = Node(1, int(1e9))

    def modify(self, l, r, v, node=None):
        if l > r:
            return
        if node is None:
            node = self.root
        if node.l >= l and node.r <= r:
            node.v = v
            node.add = v
            return
        self.pushdown(node)
        if l <= node.mid:
            self.modify(l, r, v, node.left)
        if r > node.mid:
            self.modify(l, r, v, node.right)
        self.pushup(node)

    def query(self, l, r, node=None):
        if l > r:
            return 0
        if node is None:
            node = self.root
        if node.l >= l and node.r <= r:
            return node.v
        self.pushdown(node)
        v = 0
        if l <= node.mid:
            v = max(v, self.query(l, r, node.left))
        if r > node.mid:
            v = max(v, self.query(l, r, node.right))
        return v

    def pushup(self, node):
        node.v = max(node.left.v, node.right.v)

    def pushdown(self, node):
        if node.left is None:
            node.left = Node(node.l, node.mid)
        if node.right is None:
            node.right = Node(node.mid + 1, node.r)
        if node.add:
            node.left.v = node.add
            node.right.v = node.add
            node.left.add = node.add
            node.right.add = node.add
            node.add = 0


class Solution:
    def fallingSquares(self, positions: List[List[int]]) -> List[int]:
        ans = []
        mx = 0
        tree = SegmentTree()
        for l, w in positions:
            r = l + w - 1
            h = tree.query(l, r) + w
            mx = max(mx, h)
            ans.append(mx)
            tree.modify(l, r, h)
        return ans
speed

复杂度分析

指标值
时间complexity is O(N log N) because each square involves a log N query and update on the segment tree across N squares. Space complexity is O(N) for storing the compressed coordinates and segment tree nodes.
空间O(N)
psychology

面试官常问的追问

外企场景
  • question_mark

    Check if candidates handle very large X coordinates efficiently.

  • question_mark

    Look for proper use of range maximum queries using a segment tree or ordered set.

  • question_mark

    Watch for mistakes in determining whether squares actually stack or just touch sides.

warning

常见陷阱

外企场景
  • error

    Failing to compress coordinates, causing memory overflow for large lefti values.

  • error

    Mistaking side contact for stacking, resulting in incorrect height calculation.

  • error

    Updating heights incorrectly across overlapping intervals, which produces wrong maximum heights.

swap_horiz

进阶变体

外企场景
  • arrow_right_alt

    Falling rectangles instead of squares, where width varies for each drop.

  • arrow_right_alt

    Allowing squares to slide horizontally if they touch a side, introducing physics-based landing rules.

  • arrow_right_alt

    Computing total area covered by all stacked squares after each drop instead of just maximum height.

help

常见问题

外企场景

继续练习

#729 我的日程安排表 I#731 我的日程安排表 II#850 矩形面积 II
category

继续题型

数组

在同题型下练更多边界和追问。

arrow_forwardauto_awesome

继续模式

数组·结合·segment·树

用同一解题框架扩展到更多题目。

arrow_forwardsignal_cellular_alt

同难度题单

困难

按当前难度继续强化稳定输出。

arrow_forward
掉落的方块题解：数组·结合·segment·树 | LeetCode #699 困难