代码随想录第三十一天| 56. 合并区间 738.单调递增的数字

56. 合并区间

题目描述

给定一个区间的集合 intervals，请合并所有重叠的区间。

---

解题思路

1. 排序区间

   • 按照每个区间的起点 start 升序排序，便于后续合并。

2. 合并区间

   • 使用两个变量 start 和 right 分别记录当前区间的起点和终点。
   • 遍历排序后的区间：
     • 如果当前区间的起点 intervals[i][0] 小于或等于 right，说明当前区间与之前的区间重叠，更新 right 为两者终点的最大值。
     • 如果不重叠，将当前区间 [start, right] 添加到结果中，并更新 start 和 right 为当前区间的起点和终点。

3. 时间复杂度

   • 排序时间复杂度为 O(n log n)。
   • 遍历时间复杂度为 O(n)。
   • 总时间复杂度为 O(n log n)，空间复杂度为 O(n)。

---

Java代码

class Solution {public int[][] merge(int[][] intervals) {List<int[]> res = new LinkedList<>();Arrays.sort(intervals , (a,b) ->{return Integer.compare(a[0],b[0]);});int start = intervals[0][0];int right = intervals[0][1];for(int i = 1;i<intervals.length;i++){if(intervals[i][0]<=right){right = Math.max(intervals[i][1],right);}else {res.add(new int[]{start,right});start = intervals[i][0];right = intervals[i][1];}}res.add(new int[]{start,right});return res.toArray(new int[res.size()][]);}
}

738.单调递增的数字

题目：给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
解题思路：
代码：

class Solution {public int monotoneIncreasingDigits(int n) {String[] strings = (n + "").split("");int start = strings.length;for(int i = strings.length-1;i>0;i--){if(Integer.parseInt(strings[i]) < Integer.parseInt(strings[i-1])){strings[i-1] = (Integer.parseInt(strings[i-1])-1) + "";start = i;}}for(int i =start;i<strings.length;i++){strings[i] = "9";}return Integer.parseInt(String.join("",strings));}
}

class Solution {public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] chars = s.toCharArray();int start = chars.length;for(int i = chars.length-1;i>0;i--){if(chars[i] < chars[i-1]){chars[i-1]--;start = i;}}for(int i =start;i<chars.length;i++){chars[i] = '9';}return Integer.parseInt(String.valueOf(chars));}
}