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

56. 合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        //对区间按照右边界排序
        Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));

        List<int[]> p = new LinkedList<>();

        int l = intervals[0][0],r = intervals[0][1];
        for(int i = 1;i < intervals.length;i++){
            // 合并区间
            if(intervals[i][0] <= r){
                r = Math.max(r,intervals[i][1]);
            }else{
                // 添加区间
                p.add(new int[]{l,r});
                //定义新的区间的边界
                l = intervals[i][0];
                r = intervals[i][1];
            }
        }
        //处理最后一个区间
        p.add(new int[]{l,r});
        return p.toArray(new int[p.size()][]);
    }
}

738.单调递增的数字

思路：只想到了一个暴力，还超时了~，这里的思路很巧妙，大概意思就是找最高位不符合数字递增的地方，然后把后面的位都变成最大值9，此时，我们找最高位就涉及到一个遍历顺序的问题，如果从头开始遍历，比如332，我们找到第二位是不符合条件的，3<2的，所以此时要将3-1，2->9,可是这样遍历得到的是329还是不符合题目要求，所以只能从后面开始遍历。详细解释看这里：代码随想录

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