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

56. 合并区间

力扣题目链接(opens new window)

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

示例 1:

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: intervals = [[1,4],[4,5]]输出: [[1,5]]解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

 这道题就需要一个定义一个左区间和右区间来判断，如果加入res后，重新定义左右区间，是为了在重叠区间时右区间一直累加，

** 时间复杂度 ： O(NlogN) 排序需要O(NlogN) 空间复杂度 ： O(logN) java 的内置排序是快速排序 需要 O(logN)空间 */ class Solution { public int[][] merge(int[][] intervals) { List<int[]> res = new LinkedList<>(); //按照左边界排序 Arrays.sort(intervals, (x, y) -> Integer pare(x[0], y[0])); //initial start 是最小左边界 int start = intervals[0][0]; int rightmostRightBound = intervals[0][1]; for (int i = 1; i < intervals.length; i++) { //如果左边界大于最大右边界 if (intervals[i][0] > rightmostRightBound) { //加入区间 并且更新start res.add(new int[]{start, rightmostRightBound}); start = intervals[i][0]; rightmostRightBound = intervals[i][1]; } else { //更新最大右边界 rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]); } } res.add(new int[]{start, rightmostRightBound}); return res.toArray(new int[res.size()][]); } } 738.单调递增的数字

力扣题目链接(opens new window)

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

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

示例 1:

输入: N = 10输出: 9

示例 2:

输入: N = 1234输出: 1234

示例 3:

输入: N = 332输出: 299

说明: N 是在 [0, 10^9] 范围内的一个整数。

 本题只要想清楚个例，例如98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]减一，strNum[i]赋值9，这样这个整数就是89。就可以很自然想到对应的贪心解法了。

就是从后向前遍历，前面减1，后面变9

这道题要设置一个start来表示应该从哪里开始赋值9，如果没有的话例如100显示的就是90，因00是相等的，没有进入if判断，所以最后一个数字依然是0 

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