这道题是经典的离线查询(Offline Query)配合优先队列(PriorityQueue)的题目。

核心思路

如果我们对每个查询都遍历一遍所有区间,时间复杂度是 O(Q times N),会超时。我们需要利用排序和堆来优化。

策略:
1.  排序(离线处理):
    *   将 intervals 按左端点从小到大排序。
    *   将 queries 按查询值从小到大排序(但要保留原始索引,以便最后还原结果)。

2.  优先队列(最小堆):
    *   我们需要快速找到包含当前查询点且长度最小的区间。
    *   堆中存储候选区间。堆顶始终是长度最小的区间。
    *   堆中的元素可以是 {区间长度, 区间右端点}。

3.  滑动窗口思想:
    *   随着查询值从小到大增加,我们只需要不断往堆里添加新的区间(左端点 le 当前查询值)。
    *   同时,我们需要从堆里移除那些已经“过期”的区间(右端点  a[0] - b[0]);
        
        // 2. 处理查询
        // 创建一个新的数组存储 {查询值, 原始索引}
        int[][] sortedQueries = new int[queries.length][2];
        for (int i = 0; i  a[0] - b[0]);
        
        int[] res = new int[queries.length];
        // 默认结果为 -1
        Arrays.fill(res, -1);
        
        // 3. 最小堆
        // 存储 {区间长度, 区间右端点}
        // 按照区间长度升序排列
        PriorityQueue pq = new PriorityQueue((a, b) -> a[0] - b[0]);
        
        int intervalIdx = 0; // 指向 intervals 的指针
        
        // 4. 遍历每个查询(从小到大)
        for (int[] q : sortedQueries) {
            int queryVal = q[0];
            int originalIdx = q[1];
            
            // A. 将所有左端点 = 2,无需清理。
    *   结果:堆顶长度 3。

3.  处理 q=3:
    *   入堆:[3,6] (len=4)。堆:{3,4}, {4,4}, {4,6}。
    *   清理:堆顶右端点 4 >= 3,无需清理。
    *   结果:堆顶长度 3。

4.  处理 q=4:
    *   入堆:[4,4] (len=1)。堆:{1,4}, {3,4}, {4,4}, {4,6}。
    *   清理:堆顶右端点 4 >= 4,无需清理。
    *   结果:堆顶长度 1。

5.  处理 q=5:
    *   入堆:无更多区间。
    *   清理:
        *   堆顶 {1,4},右端点 4 = 5,停止。
    *   结果:堆顶长度 4。

最终结果:[3, 3, 1, 4]。

 

Logo

欢迎加入DeepSeek 技术社区。在这里,你可以找到志同道合的朋友,共同探索AI技术的奥秘。

更多推荐