【力扣题解】436. 寻找右区间
😊博主目前也在学习,有错误欢迎指正😊
🌈保持热爱 奔赴星海🌈
文章目录
-
- 一、题目
-
- 1、题目描述
- 2、基础框架
- 3、原题链接
- 二、解题报告
-
- 1、思路分析
- 2、代码详解
- 三、本题知识
一、题目
1、题目描述
给你一个区间数组 intervals ,其中 intervals[i] = [starti, endi] ,且每个 starti 都 不同 。
区间 i 的 右侧区间 可以记作区间 j ,并满足 startj >= endi ,且 startj 最小化 。
返回一个由每个区间 i 的 右侧区间 在 intervals 中对应下标组成的数组。如果某个区间 i 不存在对应的 右侧区间 ,则下标 i 处的值设为 -1 。
2、基础框架
- Java版本框架代码如下:
class Solution { public int[] findRightInterval(int[][] intervals) { } }
3、原题链接
436. 寻找右区间
二、解题报告
1、思路分析
(1)遍历intervals数组,取出intervals[i][1],把intervals[i][1]和每个元素的第二个元素比较,即intervals[j][0]。若满足intervals[i][1] <= intervals[j][0]则记录下来,当有多个intervals[j][0]满足intervals[i][1] <= intervals[j][0]时,取最小值。
(2)若没有满足intervals[i][1] <= intervals[j][0]的元素则res[i]的值为-1;
2、代码详解
class Solution { public int[] findRightInterval(int[][] intervals) { int n = intervals.length; int[] res = new int[n]; for(int i = 0;i < n;i++) { int tmp = Integer.MAX_VALUE; for(int j = 0;j < n;j++) { if(intervals[i][1] <= intervals[j][0]) { if(tmp > intervals[j][0]) { res[i] = j; tmp = intervals[j][0]; } }else if(j == n - 1 && tmp == Integer.MAX_VALUE) { res[i] = -1; } } } return res; }}
三、本题知识
遍历+判断统计