力扣爆刷第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));}
}