案例

GodX...大约 9 分钟

汇总区间(简)

给定一个 无重复元素 的有序整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

"a->b" ，如果 a != b
"a" ，如果 a == b

示例 1：

输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：区间范围是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

示例 2：

输入：nums = [0,2,3,4,6,8,9]
输出：["0","2->4","6","8->9"]
解释：区间范围是：
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"

提示：

0 <= nums.length <= 20
-231 <= nums[i] <= 231 - 1
nums 中的所有值都 互不相同
nums 按升序排列

解题思路

首先，判断输入的数组是否为空，如果为空，就返回一个空数组
然后，定义一个答案数组ans，和两个指针L和R，分别指向数组的第一个和第二个元素
定义一个辅助函数handlePush，用来将L和R-1之间的连续区间添加到ans中，如果L和R-1相等，就只添加一个元素，否则添加一个范围字符串
接着，遍历数组，计算R和R-1之间的差值gap，如果gap大于1，说明L和R-1之间的区间已经结束，就调用handlePush函数，然后将L移动到R的位置
最后，将L和R-1之间的最后一个区间也添加到ans中，返回ans数组

优化空间

循环的条件是R < nums.length，所以当R等于nums.length时，循环就停止了，此时L和R-1之间的区间还没有被处理，所以需要在循环外面再调用一次handlePush函数，将最后一个区间也加入到ans数组中。

我们可以使用分组循环进行优化，具体看看概述中的分组循环

self

/**
 * @param {number[]} nums
 * @return {string[]}
 */
var summaryRanges = function (nums) {
    if (nums.length === 0) return []
    const ans = [];
    let L = 0;
    let R = 1;
    function handlePush() {
        if (nums[L] === nums[R - 1]) {
            ans.push(nums[L].toString())
        } else {
            ans.push(nums[L] + '->' + nums[R - 1]);
        }
    }
    while (R < nums.length) {
        const gap = nums[R] - nums[R - 1];
        if (gap > 1) {
            handlePush()
            L = R;
        }
        R++;
    }
    handlePush()
    return ans
};

优化后

function summaryRanges(nums) {
    // 用于存储最终结果的数组
    let ans = [];
    // 初始化迭代器 i 为 0，表示从数组的第一个元素开始遍历
    let i = 0;
    // 获取数组的长度，方便后续迭代使用
    let n = nums.length;

    // 使用 while 循环进行迭代，直到遍历完整个数组
    while (i < n) {
        // 记录当前连续范围的起始索引
        let start = i;

        // 使用内部的 while 循环，查找当前连续范围的结束索引
        while (i < n - 1 && nums[i] + 1 === nums[i + 1]) {
            i++;
        }
        // 将当前连续范围的起始值和结束值组成字符串，加入结果数组
        ans.push(i === start ? `${nums[start]}` : `${nums[start]}->${nums[i]}`);
        
        // 继续迭代下一个元素
        i++;
    }

    // 返回整理好的结果数组
    return ans;
}

合并区间(中)

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

解题思路

通过根据区间的起始时间进行排序
然后依次比较每个区间与前一个区间。
如果当前区间的开始时间在前一个区间的结束时间之后，代表它们不重叠，可以将前一个区间添加到结果数组中。
如果它们重叠，前一个区间的结束时间将延长到其自身结束时间和当前区间结束时间的最大值。
最后将最后一个区间添加到结果数组中。

var merge = function (intervals) {
    // 按照区间起始值进行升序排序
    intervals.sort((a, b) => a[0] - b[0]);
    
    // 初始化变量，用于迭代比较和合并区间
    let prev = intervals[0];
    let result = [];
    
    // 遍历排序后的区间数组
    for (let i = 1; i < intervals.length; i++) {
        let cur = intervals[i];
        
        // 如果当前区间的起始值大于前一个区间的结束值，表示两区间不重叠
        if (cur[0] > prev[1]) {
            // 将前一个区间添加到结果数组中，并更新prev为当前区间
            result.push(prev);
            prev = cur;
        } else {
            // 如果两区间重叠，更新前一个区间的结束值为当前区间结束值的较大值
            prev[1] = Math.max(cur[1], prev[1]);
        }
    }
    
    // 将最后一个合并后的区间添加到结果数组中
    result.push(prev);
    
    // 返回合并后的区间数组
    return result;
};

插入区间(中)

给你一个 无重叠的 *，*按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1：

输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]

示例 2：

输入：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] 重叠。

示例 3：

输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]

示例 4：

输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]

示例 5：

输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]

提示：

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= intervals[i][0] <= intervals[i][1] <= 105
intervals 根据 intervals[i][0] 按升序排列
newInterval.length == 2
0 <= newInterval[0] <= newInterval[1] <= 105

解题思路

方法一

插入后排序，然后利用合并区间的方法。

方法二

用指针去扫 intervals，最多可能有三个阶段：

不重叠的绿区间，在蓝区间的左边
有重叠的绿区间
不重叠的绿区间，在蓝区间的右边

具体流程：

第一个while循环是将所有在新区间之前且不重叠的区间加入到答案数组中。
第二个while循环是将所有与新区间有重叠的区间合并成一个新的区间，更新新区间的起点和终点为最小和最大的值。
第三个while循环是将所有在新区间之后且不重叠的区间加入到答案数组中。

方法一

var insert = function(intervals, newInterval) {
    const arr = [...intervals,newInterval];
    arr.sort((a,b) => a[0] - b[0]);
    const ans = [];
    let prev = arr[0];
    for(let i = 1;i < arr.length;i++) {
        const curr = arr[i];
        if(prev[1] < curr[0]) {
            ans.push(prev);
            prev = curr;
        } else {
            prev[1] = Math.max(prev[1],curr[1])
        }
    }
    ans.push(prev);
    return ans
};

方法二

var insert = function(intervals, newInterval) {
    const ans = []; // 存储最终结果的数组
    let i = 0; // 遍历intervals的指针
    const len = intervals.length; // 区间列表的长度

    // 遍历区间列表，将在新区间之前的区间加入结果数组
    while (i < len && intervals[i][1] < newInterval[0]) {
        ans.push(intervals[i++]);
    }

    // 合并重叠区间，更新新区间的起始和结束位置
    while (i < len && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }

    // 将合并后的新区间加入结果数组
    ans.push(newInterval);

    // 将剩余的区间加入结果数组
    while (i < len) {
        ans.push(intervals[i++]);
    }

    // 返回最终结果数组
    return ans;
};

用最少数量的箭引爆气球(中)

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end，且满足 xstart ≤ x ≤ x``end，则该气球会被引爆。可以射出的弓箭的数量 没有限制 。弓箭一旦被射出之后，可以无限地前进。

给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数 。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。

提示:

1 <= points.length <= 105
points[i].length == 2
-231 <= xstart < xend <= 231 - 1

解题思路

首先，对于右端点最小的那个区间，如果想要用箭穿过它，那么一定从它的右端点穿过（从右端点穿过才只会穿过更多的区间）。
接下来，对于这只箭能未能穿过的区间，再从中找出右端点最小的区间。对于这只箭未能穿过的区间，如此往复的找下去。最终我们使用的箭数就是最少的。

var findMinArrowShots = function(points) {
    if (points.length == 0) return 0;
    // 按照右边界排序
    points.sort((a, b) => a[1] - b[1]);
    let count = 1; // 至少需要一支箭
    let end = points[0][1]; // 当前箭的位置
    for (let i = 1; i < points.length; i++) {
        // 如果当前气球的左边界大于箭的位置，说明不能被射穿，需要另外一支箭
        if (points[i][0] > end) {
            count++;
            end = points[i][1]; // 更新箭的位置
        }
    }
    return count;
};

昵称

邮箱

网址

按正序
按倒序
按热度

案例

汇总区间(简)

合并区间(中)

插入区间(中)

用最少数量的箭引爆气球(中)

预览: