重生之我在代码随想录刷算法第二十七天 | 56. 合并区间、738.单调递增的数字

参考文献链接：代码随想录

本人代码是Java版本的，如有别的版本需要请上代码随想录网站查看。

56. 合并区间

力扣题目链接

解题思路

这道题目和昨天的重叠区间差不多，我们还是先把左边界排序，然后遍历数组，如何重合就合并，不重合就添加到result中。

代码示例

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new LinkedList<>();
        Arrays.sort(intervals,(a,b) -> 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(right < intervals[i][0]){
                res.add(new int[]{start,right});
                start = intervals[i][0];
                right = intervals[i][1];
            }else{
                right = Math.max(right,intervals[i][1]);
            }
        }
        res.add(new int[]{start,right});
        return res.toArray(new int[res.size()][]);
    }
}

738.单调递增的数字

力扣题目链接

解题思路

这道题目我最初有些思路，从前往后遍历，只要我判断到某一个数比它后一个数大，那我就把当前数减1.然后后面数全变9即可。但我遇到了668841后，668799就不对了，应该是667999。我的思路对于这种例子来说就有问题，它前几个数相等但后面变小了。所以很难办，应该从后往前遍历。

从后往前的话就简单了，当前一个大于后一个，前一个就减1，并且把后一个变为9。

代码示例

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));
    }
}