56. 合并区间
判断重叠区间问题，与452和435是一个套路
方法1：fff
看方法2：fff优化版
- 使用
currentInterval来追踪当前合并的区间，而不是在原数组上修改值。 - 每当找到一个不重叠的区间时，将
currentInterval添加到result，并开始一个新的currentInterval。
class Solution {public int[][] merge(int[][] intervals) {// 方法1：fff
// if (intervals.length == 1){
// return intervals;
// }
// Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
// int[][] result = new int[intervals.length][];
// int row = 0;
// for (int i = 0; i < intervals.length - 1; i++) {
// if (intervals[i + 1][0] <= intervals[i][1]){
// intervals[i + 1][0] = Math.min(intervals[i][0],intervals[i + 1][0]);
// intervals[i + 1][1] = Math.max(intervals[i][1],intervals[i + 1][1]);
// } else {
// result[row++] = intervals[i];
// }
// }
// result[row] = intervals[intervals.length - 1];
// int[][] res = new int[row+1][];
// int i = 0;
// for (int[] r : result){
// if (r == null){
// break;
// }
// res[i++] = r;
// }
// return res;// 方法2：fff优化版if (intervals.length == 1){return intervals;}// 排序的时间复杂度是O(n log n), n是intervals数组的长度。Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));List<int[]> result = new LinkedList<>();int[] currentInterval = intervals[0]; // 使用currentInterval来追踪当前合并的区间，而不是在原数组上修改值。for (int i = 1; i < intervals.length ; i++) {if (intervals[i][0] <= currentInterval[1]){// 合并currentInterval[1] = Math.max(currentInterval[1], intervals[i][1]);} else {result.add(currentInterval);currentInterval = intervals[i];}}result.add(currentInterval);return result.toArray(new int[result.size()][]);}
}方法3：
看方法2或者3都可以，复杂度是一样的。都挺好的。
- 代码结构：方法3实现直接使用
LinkedList<int[]>的getLast()和removeLast()来获取和更新最后一个合并区间，代码更加简洁且避免了在原数组上修改数据。 - 操作顺序：方法3实现中，每次更新最后一个区间的值时，先移除再添加，这样减少了代码复杂性；而方法2实现会在原数组上更新，代码稍显繁琐。
class Solution {public int[][] merge(int[][] intervals) {//方法3：LinkedList<int[]> res = new LinkedList<>();Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));res.add(intervals[0]);for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] <= res.getLast()[1]) {int start = res.getLast()[0];int end = Math.max(intervals[i][1], res.getLast()[1]);res.removeLast();res.add(new int[]{start, end});} else {res.add(intervals[i]);}}return res.toArray(new int[res.size()][]);}}738.单调递增的数字
968.监控二叉树
剩下两道明天再做，晚安
// 第三十一天的总算是结束了，直冲Day32！
