面试经典 150 题-区间

LeetCode 面试经典 150 题-区间

汇总区间

模拟

class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> res = new ArrayList<String>();
        // 处理边界 
        int n = nums.length;
        if (n == 0) {
            return res;
        }
        
        int pre = nums[0];
        for (int i = 1; i < n; i++) {
            // 添加区间
            if (nums[i] != nums[i-1] + 1) {
                // 区间内包含多个数字
                if (pre != nums[i-1]) {
                    String str = pre + "->" + nums[i-1];
                    res.add(str);
                } else {
                    res.add(String.valueOf(pre));
                }
                // 更新区间起始
                pre = nums[i];
            } 
        }

        // 处理最后一个区间
        if (pre != nums[n - 1]) {
            res.add(pre + "->" + nums[n - 1]);
        } else {
            res.add(String.valueOf(pre));
        }

        return res;
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

合并区间

贪心

1. 对区间按照起始点进行排序。
2. 遍历区间，如果当前区间的起始位置小于上一个区间的结束位置，则说明可以合并区间，将区间的结束位置置为两区间结束位置的较大值。否则直接加入结果集。

class Solution {
    public int[][] merge(int[][] intervals) {
        // 按照起始位置进行排序
        Arrays.sort(intervals, (row1, row2) -> Integer.compare(row1[0], row2[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()][]);
    }
}

• 时间复杂度：O(nlogn)
• 空间复杂度：O(logn)

插入区间

模拟

1. 维护待插入区间的范围，维护是否在遍历过程中插入的标记；
2. 遍历区间：
   • 在插入区间右侧且无交集：如果还未插入，则插入，然后将当前区间加入结果；
   • 在插入区间左侧且无交集：当前区间加入结果集；
   • 有重叠：更新待插入区间的范围；
3. 如果在遍历区间的时候没有插入新区间，说明整个区间都是重叠的，插入。
4. 返回结果。

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        // 维护待插入区间的范围
        int left = newInterval[0];
        int right = newInterval[1];
        // 标记是否在遍历过程中插入
        boolean placed = false;
        // 遍历区间
        List<int[]> res = new ArrayList<>();
        for (int[] interval : intervals) {
            // 在插入区间右侧且无交集
            if (interval[0] > right) {
                // 插入
                if (!placed) {
                    res.add(new int[]{left, right});
                    placed = true;
                }
                // 插入当前区间
                res.add(interval);

            } else if (interval[1] < left) {
                // 在插入区间左侧且无交集
                res.add(interval);
            } else {
                // 与插入区间有交集，计算其并集
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        
        // 如果再循环中未被插入，即整个区间都是重叠的
        if (!placed) {
            res.add(new int[]{left, right});
        }

        // 返回结果
        return res.toArray(new int[res.size()][]);
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)

用最少数量的箭引爆气球

贪心

将坐标按结束位置升序排序。对于第一个区间，假设弓箭射在其结束位置，往后依次遍历每个区间，如果弓箭的坐标小于区间的起始坐标，说明需要新的弓箭。

class Solution {
    public int findMinArrowShots(int[][] points) {
        // 按结束位置进行排序
        Arrays.sort(points, (p1, p2) -> Integer.compare(p1[1], p2[1]));
        
        // 遍历坐标
        int ans = 1;
        int arrow = points[0][1];   // 箭射在第一个球的结束位置
        for (int i = 1; i < points.length; i++) {
            // 需要一支新的箭
            if (points[i][0] > arrow) {
                ans++;
                arrow = points[i][1];   // 更新弓箭位置
            }
        }

        return ans;
    }
}

相当于合并区间的时候取交集，最后返回交集区间数。

• 时间复杂度：O(nlogn)
• 空间复杂度：O(logn)

总结

1. 排序

   很多区间类问题都要求按区间的起始点或结束点排序，这是解题的第一步。排序后，可以更容易地判断区间之间的关系（是否有交集，是否可以合并等）。

   • 排序依据：通常按区间的起始位置排序，或按结束位置排序。
   • 排序后，简化问题：排序后的区间更容易处理，很多问题可以转换成遍历排序后的区间，逐一进行合并或插入。

2. 区间的合并与插入

   • 合并区间：遍历所有区间，遇到有交集的区间时，将它们合并成一个新区间。-
   • 插入区间：对于给定的新区间，遍历现有区间，判断是否存在交集，若有交集则更新新区间的范围，否则直接插入。

3. 贪心策略

   贪心算法非常适合用于区间问题，特别是涉及到最小化操作的题目，如最少箭数射爆气球、区间调度问题等。通过选择当前最优的局部解来达到全局最优。典型的做法是按结束点或起始点对区间进行排序，之后选择最合适的区间进行处理。

4. 区间的交集与并集

   • 交集：两个区间是否有交集可以通过比较它们的起始点和结束点来判断。
   • 并集：若两个区间有交集，则它们的并集区间就是从最小的起点到最大的终点。

5. 边界条件处理

   许多区间问题的边界条件处理需要特别注意，如空区间的情况、只有一个区间的情况等。