盒子
盒子

57_插入区间_leetcode

给出一个无重叠的 ,按照区间起始端点排序的区间列表。
在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)

输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
输出: [[1,5],[6,9]]
输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出: [[1,2],[3,10],[12,16]]
解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

题解: 栈+队列 将原始数据扩容,然后按照题目57的思路解决即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
int[][] newIntervals = new int[intervals.length + 1][];
System.arraycopy(intervals, 0, newIntervals, 0, intervals.length);
newIntervals[intervals.length] = newInterval;

Arrays.sort(newIntervals, (a, b) -> a[0] - b[0]);
Stack<int[]> stack = new Stack<>();
for (int[] num : newIntervals) {
if (stack.isEmpty()) {
stack.push(num);
continue;
}
int[] arr = stack.peek();
if (arr[1] >= num[0]) {
int[] combine = {arr[0], Math.max(arr[1], num[1])};
stack.pop();
stack.push(combine);
} else {
stack.push(num);
}
}
return stack.toArray(new int[0][]);
}
}

AC传送门leetcode

支持一下
扫一扫,支持沈健
  • 微信扫一扫
  • 支付宝扫一扫