Hard

题目描述

存在一条无限长的数线，原点位于 0，向正 x 轴方向延伸。

给你一个二维数组 queries，包含两种类型的查询：

  • 对于类型 1 的查询，queries[i] = [1, x]。在距离原点 x 的位置建造一个障碍物。保证查询时在距离 x 处没有障碍物。
  • 对于类型 2 的查询，queries[i] = [2, x, sz]。检查是否可以在范围 [0, x] 内的任何位置放置一个大小为 sz 的区块，使得区块完全位于范围 [0, x] 内。区块不能与任何障碍物相交，但可以接触。注意，你实际上并不放置区块。查询是独立的。

返回一个布尔数组 results，其中 results[i] 为 true 表示可以放置第 i 个类型 2 查询中指定的区块，否则为 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 * 10^4
  • 2 <= queries[i].length <= 3
  • 1 <= queries[i][0] <= 2
  • 1 <= x, sz <= min(5 * 10^4, 3 * queries.length)
  • 对于类型 1 的查询，保证查询时在距离 x 处不存在障碍物
  • 保证至少有一个类型 2 的查询

解题思路

这道题的核心思路是维护每个位置到下一个障碍物的距离。

解题思路：

  1. 核心观察：要在区间 [0, x] 中放置大小为 sz 的区块，我们需要找到一个连续的空间，其长度至少为 sz。如果我们知道每个位置到下一个障碍物的距离，那么问题就转化为：在区间 [0, x-sz] 中是否存在某个位置 i，使得从位置 i 到下一个障碍物的距离大于等于 sz。

  2. 数据结构选择：使用线段树来维护区间最大值。对于每个位置 i，我们维护 d[i] 表示从位置 i 到下一个障碍物的距离。

  3. 算法流程：

    • 初始化时，假设在很远的地方（如 50001）有一个虚拟障碍物
    • 对于类型 1 查询（添加障碍物）：在位置 x 添加障碍物，更新所有受影响位置的 d 值
    • 对于类型 2 查询（检查是否可放置区块）：查询区间 [0, x-sz] 的最大 d 值是否大于等于 sz

  4. 优化细节：

    • 使用坐标压缩，只处理查询中出现的坐标
    • 线段树支持单点更新和区间查询最大值
    • 添加障碍物时，需要更新该障碍物前面所有位置到下一个障碍物的距离

代码实现

class Solution {
public:
    vector<bool> getResults(vector<vector<int>>& queries) {
        set<int> obstacles;
        obstacles.insert(50001); // 虚拟障碍物
        
        vector<bool> results;
        
        for (auto& query : queries) {
            if (query[0] == 1) {
                // 添加障碍物
                obstacles.insert(query[1]);
            } else {
                // 检查是否可以放置区块
                int x = query[1], sz = query[2];
                if (sz > x) {
                    results.push_back(false);
                    continue;
                }
                
                bool canPlace = false;
                // 检查每个可能的起始位置
                for (int start = 0; start <= x - sz; start++) {
                    // 找到start位置之后的第一个障碍物
                    auto it = obstacles.upper_bound(start);
                    int nextObstacle = *it;
                    
                    if (start + sz <= min(nextObstacle, x)) {
                        canPlace = true;
                        break;
                    }
                }
                results.push_back(canPlace);
            }
        }
        
        return results;
    }
};

class Solution:
    def getResults(self, queries: List[List[int]]) -> List[bool]:
        import bisect
        
        obstacles = [50001]  # 虚拟障碍物
        results = []
        
        for query in queries:
            if query[0] == 1:
                # 添加障碍物
                bisect.insort(obstacles, query[1])
            else:
                # 检查是否可以放置区块
                x, sz = query[1], query[2]
                if sz > x:
                    results.append(False)
                    continue
                
                can_place = False
                # 检查每个可能的起始位置
                for start in range(x - sz + 1):
                    # 找到start位置之后的第一个障碍物
                    idx = bisect.bisect_right(obstacles, start)
                    next_obstacle = obstacles[idx]
                    
                    if start + sz <= min(next_obstacle, x):
                        can_place = True
                        break
                
                results.append(can_place)
        
        return results

public class Solution {
    public IList<bool> GetResults(int[][] queries) {
        var obstacles = new SortedSet<int>();
        obstacles.Add(50001); // 虚拟障碍物
        
        var results = new List<bool>();
        
        foreach (var query in queries) {
            if (query[0] == 1) {
                // 添加障碍物
                obstacles.Add(query[1]);
            } else {
                // 检查是否可以放置区块
                int x = query[1], sz = query[2];
                if (sz > x) {
                    results.Add(false);
                    continue;
                }
                
                bool canPlace = false;
                // 检查每个可能的起始位置
                for (int start = 0; start <= x - sz; start++) {
                    // 找到start位置之后的第一个障碍物
                    int nextObstacle = obstacles.GetViewBetween(start + 1, int.MaxValue).Min;
                    
                    if (start + sz <= Math.Min(nextObstacle, x)) {
                        canPlace = true;
                        break;
                    }
                }
                results.Add(canPlace);
            }
        }
        
        return results;
    }
}

var getResults = function(queries) {
    const obstacles = new Set([50001]); // 虚拟障碍物
    const results = [];
    
    for (const query of queries) {
        if (query[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × m)，其中 n 是查询数量，m 是坐标范围。对于每个类型2查询，最坏情况下需要检查 O(m) 个起始位置
空间复杂度O(k)，其中 k 是障碍物的数量，用于存储障碍物位置

相关题目