力扣爆刷第148天之贪心算法五连刷（区间合并）

力扣爆刷第148天之贪心算法五连刷（区间合并）

一、406. 根据身高重建队列

题目链接：https://leetcode.cn/problems/queue-reconstruction-by-height/description/
思路：本题身高排序，有两个维度，一个是身高，一个是排队人数，让我们按照这两个维度对数组进行排序，使其满足要求。
维度要分开看，当身高相同时，排队元素需要升序排列，当身高不同时，身高需要降序排列（如果身高升序排列将导致排在前面的人数为0）。
按照以上要求排列好以后，一定是身高高的都排在前面，身高矮的排在后面，身高相同的排队人数升序，所以这个时候就按照排队人数把元素插入新数组，即可实现排序。

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        List<int[]> list = new ArrayList<>();
        // 身高相同数量升序，身高不同身高降序
        Arrays.sort(people, (a, b) -> {
            if(a[0] == b[0]) return a[1] - b[1];
            else return b[0] - a[0];
        });
        for(int[] nums : people) {
            list.add(nums[1], nums);
        }
        return list.toArray(new int[list.size()][]);
    }
}

二、452. 用最少数量的箭引爆气球

题目链接：https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/
思路：求用最少数量的箭引爆气球，本质上是求区间的交集有几个，交集有几个，就需要几个箭，求交集只需要先按照左区间进行排序，然后选择最小的右边界，即可。

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
        int count = 1, right = points[0][1];
        for(int[] nums : points) {
            if(nums[0] > right) {
                count++;
                right = nums[1];
            }else{
                right = Math.min(right, nums[1]);
            }
        }
        return count;
    }
}

三、435. 无重叠区间

题目链接：https://leetcode.cn/problems/non-overlapping-intervals/description/
思路：本题其实求的是无重叠区间的个数，用总区间个数减去无重叠区间的个数，即为要去掉的区间的个数。
求把多个区间去掉最少区间成为无重叠区间，首先先把所有的区间按照左边界排序，然后维护一个区间进行比较，如果当前区间的左边界位于其中，说明区间重叠了，是需要计数的，作为去掉一个区间，然后右边界改成相交的两个区间的最小的右边界，这样可以尽最大努力避免区间重叠，如果当前区间的左边界位于维护区间的右边界之外，则说明无重叠区间，又因为都是按照左边界排序的，只需要把右边界改成最右边的边界即可。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int count = 0, left = intervals[0][0], right = intervals[0][1];
        for(int i = 1; i < intervals.length; i++) {
            if(intervals[i][0] >= right) {
                right = intervals[i][1];
            }else{
                count++;
                right = Math.min(right, intervals[i][1]);
            }
        }
        return count;
    }
}

四、763. 划分字母区间

题目链接：https://leetcode.cn/problems/partition-labels/description/
思路：划分字母区间，尽可能划分较大的区间，让所有字母只出现在一个区间中，所以只需要先遍历一遍字符串，然后记录下来各个字母出现的最远距离，然后再遍历一遍字符串，不断更新当前字母最远出现的距离，只要遍历到这个距离，就划分出了一个区间。以此往复即可。

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> partitionLabels(String s) {
        int[] nums = new int[26];
        for(int i = 0; i < s.length(); i++) {
            int t = s.charAt(i) - 'a';
            nums[t] = i;
        }
        int max = 0, pro = -1;
        for(int i = 0; i < s.length(); i++) {
            max = Math.max(max, nums[s.charAt(i)-'a']);
            if(i == max) {
                list.add(i-pro);
                pro = i;
            }
        }
        return list;
    }
}

五、56. 合并区间

题目链接：https://leetcode.cn/problems/merge-intervals/
思路：和前面的几道区间相关的题来说非常简单，就是判断当前区间的左边界是否位于上一个区间之中，位于就合并，不位于就是单独的区间。

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length == 1) return intervals;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> list = new ArrayList<>();
        for(int i = 1; i < intervals.length; i++) {
            if(intervals[i][0] <= intervals[i-1][1]) {
                intervals[i][0] = intervals[i-1][0];
                intervals[i][1] = Math.max(intervals[i][1], intervals[i-1][1]);
            }else{
                int[] temp = {intervals[i-1][0], intervals[i-1][1]};
                list.add(temp);
            }
        }
        list.add(new int[]{intervals[intervals.length-1][0], intervals[intervals.length-1][1]});
        int[][] result = new int[list.size()][2];
        for(int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}

六、738. 单调递增的数字

题目链接：https://leetcode.cn/problems/monotone-increasing-digits/description/
思路：将一个数改成距离它最小的单调递增的数，其实很简单，如果两个数逆序，如53，那么最大的递增数为49，那么只需要从右边往左边找，找到第一个逆序，逆序后面的都改成9即可。

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