排序实现窗口优化+优先队列自筛选（1851. 包含每个查询的最小区间）

个人深度思考的题解，

适合俺中国小白体质！！！

class Solution {public int[] minInterval(int[][] intervals, int[] queries) {int m = intervals.length,n = queries.length;int[] ans = new int[n];Arrays.fill(ans,-1);//对数组排序本质是对下标排序int que[][] = new int[n][2];for(int i = 0;i < n;i++){que[i][0] = queries[i];que[i][1] = i;}Arrays.sort(que,(x,y) -> x[0] - y[0]);//对数组intervals根据 左端点 排序Arrays.sort(intervals,(x,y) -> x[0] - y[0]);//建立优先队列 并根据区间大小排序    注意此处的区间大小 升序排序PriorityQueue pq = new PriorityQueue<>((x,y) -> (x[1] - x[0]) - (y[1] - y[0]));int index = 0;//此下标是每一个查询 遍历全部区间//整体还是遍历查询的数字 再查询符合条件的区间 只不过呢for(int i = 0; i < n; i++){//int index = 0;//此下标是每一个查询 遍历全部区间//若查询到的数字大于等于 区间左端点 则将该区间左右端点加入到优先队列，优先队列自动会根据区间大小完成排序while(index < m && que[i][0] >= intervals[index][0]){pq.offer(new int[]{intervals[index][0],intervals[index][1]});index++;}//查询到的数字大于队列中符合左端点条件的区间右端点，则将区间 出队while(!pq.isEmpty() && que[i][0] > pq.peek()[1]){ pq.poll();}if(!pq.isEmpty()){int[] t = pq.peek();ans[que[i][1]] = t[1] - t[0] + 1;}}return ans;}
}
/*本题精髓！！！！！！！！！！！！！！！
细节点 ：为啥子本写法里面 index定义在for 外面  然后一直自增？？？这样子不会造成有的queries数字 没有在区间数组里面筛选吗？
原因点就是 在最开始 intervals 和queries数组都排序了
对于每一个queri 只会刚好扫描到 intervals左端点符合条件的边界 而之后的左端点只会更大 queri数字也只会更大 那么想要区间小
必然左端点更大一点好了 小的肯定符合 但是已经没有加入的必要了 
这就是本题的精髓！！！！由于提前进行了排序 所以对于每一个queries 越到后面，其查找的intervals 符合条件的区间数组 就越少！！！在算总的时间复杂度时，遍历queries花费n 暴力时 每一个queries对应了一次遍历intervals 所以总的时间复杂度就是平方n但是在排序后 每一个queries，对应了遍历intervals一个左右端点都符合条件的部分 至于筛选最小区间 优先队列处理了 不做计算所以遍历intervals 时间复杂度就是log 级别！！！！至于出队处理  Index就是总的intervals的下标  每一次最先筛选的是左端点  至于出队处理的 就是浪费了而已 造成的影响不大*//*
求每个查询 包含此数字的最小区间并返回区间大小 
暴力法 : 查询数字在哪个区间，查询时间复杂度n ，存在多个区间包含 筛选一下；要n个数字查询,时间复杂度n，总的时间复杂度 n平方 
咋优化？？首先就是要遍历受理每一次查询 这个n的时间复杂度是跑不了的然后就是可以优化的就是查筛选出符合条件的区间 使用优先队列 首先是筛选查询数字大于等于区间左端点就入队 大于右端点就出队 
优先队列维护的是符合在区间内 并且队列自定义 根据区间大小排序 最终队列头即为符合条件的区间*/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！