跳到主要内容

区间

区间问题的核心在于排序，通常按区间的起始位置 start 或结束位置 end 进行排序，进而简化合并或判重逻辑。

228. 汇总区间 (Summary Ranges)​

题目描述​

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

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

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

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

解题思路​

一次遍历记录起止点。

  1. 因为数组是有序的且无重复，连续的数一定满足 nums[i] == nums[i-1] + 1。
  2. 记录当前连续序列的起点 low。
  3. 当 nums[i] != nums[i-1] + 1，说明到了一个新的区间。将上一个区间输出。

Java 代码实现​

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<>();
        for (int i = 0, j = 0; j < nums.length; j++) {
            if (j + 1 < nums.length && nums[j + 1] == nums[j] + 1) continue;
            if (i == j) res.add(String.valueOf(nums[i]));
            else res.add(nums[i] + "->" + nums[j]);
            i = j + 1;
        }
        return res;
    }
}

56. 合并区间 (Merge Intervals)​

题目描述​

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

解题思路​

排序 + 贪心合并。

  1. 按区间的起始位置 start 升序排列。
  2. 遍历排序后的区间。
  3. 如果当前区间的 start 小于等于结果集中最后一个区间的 end，说明有重叠，更新结果集最后一个区间的 end 为 max(end1, end2)。
  4. 否则，新增一个区间到结果集。

Java 代码实现​

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

57. 插入区间 (Insert Interval)​

题目描述​

给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个新区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入新区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并重叠区间）。

返回插入之后的 intervals。

**注意：**你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

解题思路​

分三步走。

  1. 将所有在 newInterval 左侧 且无重叠的区间加入结果集。
  2. 对于与 newInterval 有重叠 的区间，不断更新 newInterval 的起止点：start = min(s1, s2), end = max(e1, e2)。
  3. 将最终生成的 newInterval 加入结果集。
  4. 将所有在 newInterval 右侧 且无重叠的区间加入结果集。

Java 代码实现​

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        int i = 0, n = intervals.length;
        // 左边
        while (i < n && intervals[i][1] < newInterval[0]) res.add(intervals[i++]);
        // 重叠合并
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i++][1]);
        }
        res.add(newInterval);
        // 右边
        while (i < n) res.add(intervals[i++]);
        return res.toArray(new int[res.size()][]);
    }
}

452. 用最少数量的箭引爆气球 (Minimum Number of Arrows to Burst Balloons)​

题目描述​

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

一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出的一支箭可以引爆所有满足 xstart <= x <= xend 的气球。一支箭一旦被射出之后，可以无限距离地竖直向上行驶。

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

解题思路​

贪心策略：按结束位置排序。

  1. 按区间的结束位置 end 进行升序排序。
  2. 第一箭射向第一个气球的 end（因为它必须被引爆，而射向结束位置可以尽可能多地带走后面的气球）。
  3. 遍历其余气球。如果气球的 start 大于上一箭的 pos，说明这一箭射不到该气球，需要加一箭，新箭位置设为当前气球的 end。

Java 代码实现​

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
        int count = 1, pos = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > pos) {
                count++;
                pos = points[i][1];
            }
        }
        return count;
    }
}