这道题是经典的离线查询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];// 默认结果为 -1Arrays.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. 处理 q3* 入堆[3,6] (len4)。堆{3,4}, {4,4}, {4,6}。* 清理堆顶右端点 4 3无需清理。* 结果堆顶长度 3。4. 处理 q4* 入堆[4,4] (len1)。堆{1,4}, {3,4}, {4,4}, {4,6}。* 清理堆顶右端点 4 4无需清理。* 结果堆顶长度 1。5. 处理 q5* 入堆无更多区间。* 清理* 堆顶 {1,4}右端点 4 5停止。* 结果堆顶长度 4。最终结果[3, 3, 1, 4]。