LeetCode 题解工作台
物块放置查询
有一条无限长的数轴，原点在 0 处，沿着 x 轴 正 方向无限延伸。 给你一个二维数组 queries ，它包含两种操作： 操作类型 1 ： queries[i] = [1, x] 。在距离原点 x 处建一个障碍物。数据保证当操作执行的时候，位置 x 处 没有 任何障碍物。 操作类型 2 ： que…
4
题型
0
代码语言
3
相关题
当前训练重点
困难 · 二分·搜索·答案·空间
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
有一条无限长的数轴，原点在 0 处，沿着 x 轴 正 方向无限延伸。
给你一个二维数组 queries ，它包含两种操作：
- 操作类型 1 ：
queries[i] = [1, x]。在距离原点x处建一个障碍物。数据保证当操作执行的时候，位置x处 没有 任何障碍物。 - 操作类型 2 ：
queries[i] = [2, x, sz]。判断在数轴范围[0, x]内是否可以放置一个长度为sz的物块，这个物块需要 完全 放置在范围[0, x]内。如果物块与任何障碍物有重合，那么这个物块 不能 被放置，但物块可以与障碍物刚好接触。注意，你只是进行查询，并 不是 真的放置这个物块。每个查询都是相互独立的。
请你返回一个 boolean 数组results ，如果第 i 个操作类型 2 的操作你可以放置物块，那么 results[i] 为 true ，否则为 false 。
示例 1：
输入：queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]
输出：[false,true,true]
解释：
查询 0 ，在 x = 2 处放置一个障碍物。在 x = 3 之前任何大小不超过 2 的物块都可以被放置。
示例 2：
输入：queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]
输出：[true,true,false]
解释：
- 查询 0 在
x = 7处放置一个障碍物。在x = 7之前任何大小不超过 7 的物块都可以被放置。 - 查询 2 在
x = 2处放置一个障碍物。现在，在x = 7之前任何大小不超过 5 的物块可以被放置，x = 2之前任何大小不超过 2 的物块可以被放置。
提示：
1 <= queries.length <= 15 * 1042 <= queries[i].length <= 31 <= queries[i][0] <= 21 <= x, sz <= min(5 * 104, 3 * queries.length)- 输入保证操作 1 中，
x处不会有障碍物。 - 输入保证至少有一个操作类型 2 。
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of queries and the efficiency of the segment tree or binary indexed tree updates, generally O(Q log Q) where Q is the number of queries. Space complexity is O(Q) to store obstacles and support fast queries over the number line. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Asks if you can handle an infinite number line efficiently without simulating every position.
- question_mark
Hints at using segment trees or binary indexed trees to manage obstacles.
- question_mark
Checks if you are applying binary search to find the valid placement range instead of naive iteration.
常见陷阱
外企场景- error
Attempting to check block placement by iterating over each number line position, leading to TLE.
- error
Not updating obstacle structures before type 2 queries, causing incorrect placement results.
- error
Ignoring the sequential effect of type 1 queries on type 2 queries, leading to false positives.
进阶变体
外企场景- arrow_right_alt
Queries on a finite number line with wrap-around constraints, still requiring binary search for placement.
- arrow_right_alt
Blocks with variable sizes that can be rotated, changing the binary search logic slightly.
- arrow_right_alt
Tracking multiple independent number lines with simultaneous obstacle updates, needing separate trees per line.