2023年7月18日每日一题--1851. 包含每个查询的最小区间

leetcode链接：
https://leetcode.cn/problems/minimum-interval-to-include-each-query/

题目分析

方法一： 暴力求解，尝试一下，极有可能会超时，因为hard绝对不会那么easy

方案一

class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int[] result = new int[queries.length];
        int temp, flag;

        for (int i = 0; i < queries.length; i++) {
            temp = queries[i];
            flag = -1;
            for (int j = 0; j < intervals.length; j++) {
                if (intervals[j][0] <= temp && temp <= intervals[j][1]) {
                    if (flag == -1 || flag > (intervals[j][1] - intervals[j][0] + 1) ) {
                        flag = (intervals[j][1] - intervals[j][0] + 1);
                    }
                }
            }
            result[i] = flag;
        }

        return result;
    }
}

结果

超出时间限制
34 / 42 个通过测试用例

分析

时间复杂度：
O( n * m ) <—– 时间复杂度过高，导致直接运行超时

空间复杂度：
O( m )

官方题解

官方： 包含每个查询的最小区间
Java优先级队列解题，浅显易懂

class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        //将区间按区间头从小到大排序
        Arrays.sort(intervals, (o1, o2) -> (o1[0] - o2[0]));
        //记录queries以及i，也就是queries[i]和i
        int[][] que = new int[queries.length][2];
        for(int i = 0; i < queries.length; ++i) {
            que[i][0] = queries[i];
            que[i][1] = i;
        }
        //将值排序，小的在前
        Arrays.sort(que, (o1, o2) -> (o1[0] - o2[0]));
        int[] res = new int[queries.length];
        Arrays.fill(res, -1);
        //优先级队列，区间长度小的区间优先，在队列头
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>((o1, o2) -> (o1[1] - o1[0] - o2[1] + o2[0]));
        //记录第几个区间，因为intervals和queries都是排好序的，所以用index记录目前走到哪里了
        int index = 0;
        for(int i = 0; i < queries.length; ++i) {
            //先把区间左边界小于等于queries[i]的区间加进去
            while(index < intervals.length && que[i][0] >= intervals[index][0]) {
                queue.offer(new int[]{intervals[index][0], intervals[index][1]});
                index += 1;
            }
            //再把区间右边界小于queries[i]的区间删除
            while(!queue.isEmpty() && queue.peek()[1] < que[i][0]) {
                queue.poll();
            }
            /*
            为什么不需要动index？
            正如上面的注释，intervals和queries都是排好序的
            如果这个区间不合适被删除了，是因为这个区间是在queries[i]的左面，但是之后的queries[i + 1]都比queries[i]大
            所以这个区间在以后肯定也不合适，就删除了，不再要了
            */
            if(!queue.isEmpty()) {
                int[] t = queue.peek();
                res[que[i][1]] = t[1] - t[0] + 1;  
            }
        }
        return res;

    }
}

作者：Sprinboot
链接：https://leetcode.cn/problems/minimum-interval-to-include-each-query/solution/javayou-xian-ji-dui-lie-jie-ti-qian-xian-v4s6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

个人实现： 实现较为困难，有待于更进一步的推敲
`

class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int[] result = new int[queries.length]; // 定义结果集

        // 因为涉及到对queries进行排序，所以需要确认当前int数组 索引与数值的对应关系
        int[][] queriesNew = new int[queries.length][2];
        // 将有个 queries 的相关数据放入到二维数组中，第一位放数值，第二位放索引
        for (int i = 0; i < queries.length; i++) {
            queriesNew[i][0] = queries[i];
            queriesNew[i][1] = i;
        }

        Arrays.sort(intervals, (o1, o2) -> (o1[0] - o2[0])); // 排序
        Arrays.sort(queriesNew, (o1, o2) -> (o1[0] - o2[0]));
        Arrays.fill(result, -1); // 将result所有的数值都设置为-1

        // 定义优先队列，排序函数表示将长度小是向上排序
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> (o1[1] - o1[0] - o2[1] + o2[0]));

        int index = 0; // 此处用于记录遍历 intervals 走到了那个坐标下

        for (int i = 0; i < queriesNew.length; i++) { // 对queriesNew数组进行遍历
            // 将左节点全部小于 queriesNew当前值的区间放入到优先队列中
            while (index < intervals.length && intervals[index][0] <= queriesNew[i][0]) {
                queue.add(new int[]{intervals[index][0], intervals[index][1]});
                index++;
            }
            // 将右节点小于 queriesNew当前值的区间舍弃出去，因为前面已经对其进行了排序，所以弹出的区间对应以后的数值也是没有任何作用的
            while (!queue.isEmpty() && queue.peek()[1] < queriesNew[i][0]) {
                queue.poll();
            }
            if (!queue.isEmpty()) { // 如果当前的优先队列不是空的，就说明其是有符合的数据，并且还在首位，所以直接取首位计算数值
                result[queriesNew[i][1]] = queue.peek()[1] - queue.peek()[0] + 1;
            }
        }
        return result;
    }
}