【每日一题Day269】LC1851包含每个查询的最小区间 | 排序+离线查询+小顶堆

简介: 【每日一题Day269】LC1851包含每个查询的最小区间 | 排序+离线查询+小顶堆

包含每个查询的最小区间【LC1851】

给你一个二维整数数组 intervals ,其中 intervals[i] = [lefti, righti] 表示第 i 个区间开始于 lefti 、结束于 righti(包含两侧取值,闭区间)。区间的 长度 定义为区间中包含的整数数目,更正式地表达是 righti - lefti + 1

再给你一个整数数组 queries 。第 j 个查询的答案是满足 lefti <= queries[j] <= righti长度最小区间 i 的长度 。如果不存在这样的区间,那么答案是 -1

以数组形式返回对应查询的所有答案。

排序+离线查询+小顶堆

  • 思路
  • 我们需要找到包含 queries[j]的区间的最小长度,而查询的顺序不会影响结果,因此可以采用离线查询的思路,按照某种顺序处理每个查询,以便于不需要重复访问区间,减少时间复杂度

什么顺序?

  • 按照 queries[j]从小到大的顺序处理查询,为了找到所有包含 queries[j]的区间,因此需要对所有区间按照左端点从小到大的顺序进行排序
  • 使用小顶堆存放区间信息,小顶堆以区间长度从小到大排序。
  • 对于每个查询,将可能包含该值的所有区间入堆,即如果该区间左端点小于等于queries[j],那么将其放入小顶堆中
  • 怎么获得最小区间长度?
    将所有可能区间放入后,进行判断:
  • 如果堆顶元素右端点小于queries[j],那么该区间不包含queries[j],将其弹出
  • 如果堆不为空,那么堆顶元素即为查询结果;否则,不存在合法区间,答案为-1
  • 实现
class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int n = intervals.length, m = queries.length;
        int[] res = new int[m];       
        int[][] q = new int[m][2];
        for (int i = 0; i < m; i++){
            q[i][0] = queries[i];
            q[i][1] = i;
        }
        Arrays.sort(q, (o1, o2) -> o1[0] - o2[0]);// 对查询从小到大排序
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);// 对intervals左端点从小到大排序
        int i = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);// 小顶堆,按照区间长度从小到大排序
        for (int j = 0; j < m; j++){
            int val = q[j][0], index = q[j][1];
            while (i < n && intervals[i][0] <= val){
                pq.add(new int[]{intervals[i][0], intervals[i][1], intervals[i][1] - intervals[i][0] + 1});// 将可能包含该值的所有区间入堆
                i++;
            }
            while (!pq.isEmpty() && pq.peek()[1] < val){
                pq.poll();// 将不包含该值的所有区间入堆
            }
            if (pq.isEmpty()){
                res[index] = -1;
            }else{
                res[index] = pq.peek()[2];
            }
        }
        return res;
    }
}

image.png

目录
相关文章
|
7月前
【每日一题Day176】LC2404出现最频繁的偶数元素 | 哈希表
【每日一题Day176】LC2404出现最频繁的偶数元素 | 哈希表
54 0
【每日一题Day176】LC2404出现最频繁的偶数元素 | 哈希表
|
7月前
|
算法 测试技术 C#
C++二分查找算法:包含每个查询的最小区间
C++二分查找算法:包含每个查询的最小区间
|
7月前
【每日一题Day118】LC1124表现良好的最长时间段 | 前缀和+单调栈/哈希表
【每日一题Day118】LC1124表现良好的最长时间段 | 前缀和+单调栈/哈希表
55 0
|
7月前
|
存储
【每日一题Day132】LC23633合并相似的物品 | 哈希表 排序+双指针
【每日一题Day132】LC23633合并相似的物品 | 哈希表 排序+双指针
54 0
【Leetcode -1171.从链表中删去总和值为零的连续节点 -1669.合并两个链表】
【Leetcode -1171.从链表中删去总和值为零的连续节点 -1669.合并两个链表】
101 0
|
人工智能 BI 索引
【Leetcode -598.范围求和Ⅱ -599.两个列表的最小索引总和】
【Leetcode -598.范围求和Ⅱ -599.两个列表的最小索引总和】
48 0
|
7月前
leetcode2967. 使数组成为等数数组的最小代价
leetcode2967. 使数组成为等数数组的最小代价
53 0
|
7月前
【每日一题Day215】LC1090受标签影响的最大值 | 贪心+排序+哈希表
【每日一题Day215】LC1090受标签影响的最大值 | 贪心+排序+哈希表
46 0
|
7月前
【每日一题Day303】统计点对的数目 | 哈希表+双指针
【每日一题Day303】统计点对的数目 | 哈希表+双指针
42 0
|
7月前
【每日一题Day234】LC1171从链表中删去总和值为零的连续节点 | 链表模拟 哈希表+前缀和
【每日一题Day234】LC1171从链表中删去总和值为零的连续节点 | 链表模拟 哈希表+前缀和
42 0