扫描线算法如何将二维问题降维成一维从天际线到矩形面积的LeetCode完整通关指南

扫描线算法是计算几何中最优雅的算法范式之一。它的核心思想简单得令人惊讶：用一条假想的线扫过整个平面，只在关键点停下来处理。这个朴素的想法却催生了计算复杂度理论的重大突破。1976年，Michael Shamos 和 Dan Hoey 发表了标志性的线段相交检测算法，证明了扫描线结合平衡二叉树可以在 $O(N \log N)$ 时间内判断 $N$ 条线段是否存在交点——这在当时是革命性的结果。随后，Bentley 和 Ottmann 将其扩展为报告所有交点的算法，Fortune 在 1986 年用扫描线构造 Voronoi 图，这些工作奠定了计算几何作为独立学科的基础。

在 LeetCode 上，扫描线算法是解决区间问题和几何问题的通用利器。从简单的会议室调度到复杂的天际线问题，从人口统计到矩形面积并集，一脉相承。

核心思想：事件驱动的线性扫描

扫描线算法的本质是降维打击。考虑计算矩形并集面积的问题：直接处理二维平面上 $N$ 个矩形的重叠关系极其复杂。但如果想象一条竖直线从左向右扫过整个平面，问题瞬间简化了——在任意时刻，我们只需要知道这条线与哪些矩形相交，以及相交部分的长度是多少。

两个关键概念支撑着整个算法框架：

事件点（Event Points）：扫描线需要"停下来"处理的位置。对于矩形面积问题，每个矩形的左边界和右边界都是事件点。对于区间问题，每个区间的起点和终点都是事件点。将所有事件点按坐标排序，扫描线依次经过这些点。

活动状态（Active Status）：扫描线当前位置的"快照"。对于矩形面积问题，活动状态是当前与扫描线相交的所有 y 区间。对于天际线问题，活动状态是当前所有"活跃"建筑的高度。这个状态通常用数据结构维护，使得查询和更新都能高效完成。

扫描线算法动画演示

图片来源: Wikipedia - Sweep line algorithm（Fortune 算法用扫描线构造 Voronoi 图的动画）

一维扫描线：区间问题的统一框架

一维扫描线处理的是数轴上的区间问题，其核心模式出奇地一致：在区间起点标记 +1，在区间终点标记 -1，然后扫描累积。

会议室 II（LeetCode 253）

给定一系列会议时间区间，求最少需要多少间会议室才能安排所有会议。

public int minMeetingRooms(int[][] intervals) {
    // 使用 TreeMap 自动按时间点排序
    TreeMap<Integer, Integer> timeline = new TreeMap<>();
    
    for (int[] interval : intervals) {
        timeline.put(interval[0], timeline.getOrDefault(interval[0], 0) + 1);  // 会议开始
        timeline.put(interval[1], timeline.getOrDefault(interval[1], 0) - 1);  // 会议结束
    }
    
    int rooms = 0, maxRooms = 0;
    for (int count : timeline.values()) {
        rooms += count;
        maxRooms = Math.max(maxRooms, rooms);
    }
    return maxRooms;
}

这个解法的美妙之处在于：rooms 变量在任何时刻的值，就是该时刻同时进行的会议数量。我们不需要关心具体是哪个会议开始或结束，只需要知道"有一个会议开始"或"有一个会议结束"。

时间复杂度：$O(N \log N)$，主要来自 TreeMap 的插入操作。空间复杂度：$O(N)$，存储所有事件点。

人口最多的年份（LeetCode 1854）

给定一组人的出生和死亡年份，找出人口最多的年份。

public int maximumPopulation(int[][] logs) {
    TreeMap<Integer, Integer> population = new TreeMap<>();
    
    for (int[] log : logs) {
        population.merge(log[0], 1, Integer::sum);   // 出生
        population.merge(log[1], -1, Integer::sum);  // 死亡
    }
    
    int maxPop = 0, currentPop = 0, year = 0;
    for (Map.Entry<Integer, Integer> entry : population.entrySet()) {
        currentPop += entry.getValue();
        if (currentPop > maxPop) {
            maxPop = currentPop;
            year = entry.getKey();
        }
    }
    return year;
}

与会议室问题的结构完全相同，只是语义从"会议室数量"变成了"人口数量"。

拼车问题（LeetCode 1094）

一辆车有一定容量，给定乘客上下车的时间和人数，判断能否完成所有行程。

public boolean carPooling(int[][] trips, int capacity) {
    TreeMap<Integer, Integer> passengers = new TreeMap<>();
    
    for (int[] trip : trips) {
        passengers.merge(trip[1], trip[0], Integer::sum);   // 上车
        passengers.merge(trip[2], -trip[0], Integer::sum);  // 下车
    }
    
    int current = 0;
    for (int count : passengers.values()) {
        current += count;
        if (current > capacity) return false;
    }
    return true;
}

这里的变化是：每次的"增量"不是固定的 ±1，而是上下车人数。这展示了扫描线模式的灵活性——增量可以是任意值。

我的日程安排 II（LeetCode 731）

实现一个日程安排，检测是否存在三重预订。

class MyCalendarTwo {
    private TreeMap<Integer, Integer> timeline = new TreeMap<>();
    
    public boolean book(int start, int end) {
        timeline.merge(start, 1, Integer::sum);
        timeline.merge(end, -1, Integer::sum);
        
        int count = 0;
        for (int c : timeline.values()) {
            count += c;
            if (count >= 3) {
                // 三重预订，撤销本次预订
                timeline.merge(start, -1, Integer::sum);
                timeline.merge(end, 1, Integer::sum);
                return false;
            }
        }
        return true;
    }
}

这个问题的判断条件是"累积值是否达到 3"，需要在检测到冲突时撤销操作。类似地，LeetCode 732（我的日程安排 III）要求返回最大重叠次数，解法结构相同但不需要撤销操作。

删除被覆盖区间（LeetCode 1288）

给定一组区间，删除被其他区间完全覆盖的区间，返回剩余区间数量。

public int removeCoveredIntervals(int[][] intervals) {
    // 按起点升序，起点相同时按终点降序
    Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
    
    int count = 0, maxEnd = 0;
    for (int[] interval : intervals) {
        if (interval[1] > maxEnd) {
            count++;
            maxEnd = interval[1];
        }
    }
    return count;
}

这道题展示了扫描线的另一形态：不需要显式的事件表，直接在排序后的数组上"扫描"。关键洞察是：当两个区间起点相同时，终点更长的区间会"覆盖"终点更短的区间，所以按终点降序排列可以保证先处理更长的区间。

员工空闲时间（LeetCode 759）

给定多个员工的日程安排，找出所有人都有空闲的时间段。

public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
    List<Interval> allIntervals = new ArrayList<>();
    for (List<Interval> emp : schedule) {
        allIntervals.addAll(emp);
    }
    
    // 按起点排序
    allIntervals.sort((a, b) -> a.start - b.start);
    
    List<Interval> result = new ArrayList<>();
    int end = Integer.MIN_VALUE;
    
    for (Interval interval : allIntervals) {
        if (interval.start > end && end != Integer.MIN_VALUE) {
            result.add(new Interval(end, interval.start));
        }
        end = Math.max(end, interval.end);
    }
    
    return result;
}

这道题结合了区间合并和空闲检测：先合并所有忙碌区间，再找间隙。关键是在合并过程中记录上一个区间的结束位置，当下一个区间开始时如果存在间隙就是空闲时间。

区间加法（LeetCode 370）

假设你有一个长度为 n 的数组，初始所有元素为 0。给定一系列更新操作 [start, end, inc]，表示将区间 [start, end] 内的所有元素增加 inc。返回最终数组。

public int[] getModifiedArray(int length, int[][] updates) {
    int[] result = new int[length];
    
    for (int[] update : updates) {
        int start = update[0], end = update[1], inc = update[2];
        result[start] += inc;
        if (end + 1 < length) {
            result[end + 1] -= inc;
        }
    }
    
    // 累积求和
    for (int i = 1; i < length; i++) {
        result[i] += result[i - 1];
    }
    
    return result;
}

这道题是扫描线思想在数组操作中的应用，也称为"差分数组"技术。时间复杂度从暴力的 $O(N \times K)$ 降到了 $O(N + K)$。

二维扫描线：几何问题的降维艺术

二维扫描线处理的是平面上的几何问题，需要同时在 x 和 y 两个方向上维护信息。核心思路是将二维问题分解为多个一维问题处理。

天际线问题（LeetCode 218）

给定一组建筑的左边界、右边界和高度，求城市的轮廓线。

public List<List<Integer>> getSkyline(int[][] buildings) {
    List<int[]> events = new ArrayList<>();
    for (int[] b : buildings) {
        events.add(new int[]{b[0], -b[2]});  // 左边界，高度取负表示开始
        events.add(new int[]{b[1], b[2]});   // 右边界，高度为正表示结束
    }
    
    // 按x坐标排序；x相同时，开始事件优先（高度负值更小）
    events.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
    
    List<List<Integer>> result = new ArrayList<>();
    PriorityQueue<Integer> heights = new PriorityQueue<>(Collections.reverseOrder());
    heights.offer(0);  // 地面高度
    int prevHeight = 0;
    
    for (int[] event : events) {
        int x = event[0], h = event[1];
        if (h < 0) {
            heights.offer(-h);  // 建筑开始，加入高度
        } else {
            heights.remove(h);  // 建筑结束，移除高度
        }
        
        int currHeight = heights.peek();
        if (currHeight != prevHeight) {
            result.add(Arrays.asList(x, currHeight));
            prevHeight = currHeight;
        }
    }
    return result;
}

关键洞察：天际线只会在建筑边界处发生变化。用优先队列维护当前所有"活跃"建筑的高度，每次高度变化时记录关键点。

排序技巧：为什么左边界高度取负值？因为当两个事件 x 坐标相同时，我们希望：

高建筑开始时，矮建筑还没结束（所以开始事件优先）
建筑结束时，新建筑先开始再让旧建筑结束（避免出现高度降到 0 再升上去的情况）

取负值后，开始事件（负高度）会排在结束事件（正高度）前面，完美解决排序问题。

时间复杂度：$O(N^2 \log N)$（因为 PriorityQueue.remove 是线性搜索）或 $O(N \log N)$（使用 TreeMap 优化的优先队列）。

矩形面积并集扫描线示意

图片来源: TopCoder - Line Sweep Algorithms（扫描线计算矩形并集面积的示意图）

矩形面积 II（LeetCode 850）

给定一组矩形，计算它们的并集面积。重叠区域只计算一次。

这道题需要结合扫描线和线段树，是二维扫描线的经典应用：

class SegmentTree {
    private int[] count;  // 覆盖次数
    private int[] length; // 实际覆盖长度
    private int[] nums;   // y坐标数组
    
    public SegmentTree(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        count = new int[n * 4];
        length = new int[n * 4];
    }
    
    public void update(int node, int l, int r, int ql, int qr, int val) {
        if (ql > r || qr < l) return;
        if (ql <= l && r <= qr) {
            count[node] += val;
        } else {
            int mid = (l + r) >> 1;
            update(node * 2, l, mid, ql, qr, val);
            update(node * 2 + 1, mid + 1, r, ql, qr, val);
        }
        
        if (count[node] > 0) {
            length[node] = nums[r + 1] - nums[l];
        } else if (l == r) {
            length[node] = 0;
        } else {
            length[node] = length[node * 2] + length[node * 2 + 1];
        }
    }
    
    public int query() {
        return length[1];
    }
}

public int rectangleArea(int[][] rectangles) {
    int MOD = 1_000_000_007;
    List<int[]> events = new ArrayList<>();
    Set<Integer> ySet = new HashSet<>();
    
    for (int[] rect : rectangles) {
        events.add(new int[]{rect[0], rect[1], rect[3], 1});   // 左边界
        events.add(new int[]{rect[2], rect[1], rect[3], -1});  // 右边界
        ySet.add(rect[1]);
        ySet.add(rect[3]);
    }
    
    events.sort((a, b) -> a[0] - b[0]);
    
    // y坐标离散化
    List<Integer> yList = new ArrayList<>(ySet);
    Collections.sort(yList);
    int[] yArr = yList.stream().mapToInt(i -> i).toArray();
    Map<Integer, Integer> yIndex = new HashMap<>();
    for (int i = 0; i < yArr.length; i++) {
        yIndex.put(yArr[i], i);
    }
    
    SegmentTree st = new SegmentTree(yArr);
    long area = 0;
    
    for (int i = 0; i < events.size(); i++) {
        if (i > 0) {
            int dx = events.get(i)[0] - events.get(i - 1)[0];
            area += (long) dx * st.query();
        }
        int[] e = events.get(i);
        int y1Idx = yIndex.get(e[1]);
        int y2Idx = yIndex.get(e[2]);
        st.update(1, 0, yArr.length - 2, y1Idx, y2Idx - 1, e[3]);
    }
    
    return (int) (area % MOD);
}

算法流程：

将每个矩形拆分为两个事件：左边界（添加 y 区间）和右边界（移除 y 区间）
将所有 y 坐标离散化，建立线段树
按 x 坐标处理事件，维护当前 y 方向的覆盖长度
每两个事件之间的面积 = y 覆盖长度 × x 距离

线段树的 count 数组记录每个区间被多少矩形覆盖，length 数组记录实际覆盖的 y 方向长度。当 count > 0 时，该区间完全被覆盖。

时间复杂度：$O(N \log N)$。空间复杂度：$O(N)$。

完美矩形（LeetCode 391）

判断一组矩形是否能精确拼成一个大矩形（无重叠、无间隙）。

public boolean isRectangleCover(int[][] rectangles) {
    long totalArea = 0;
    int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE;
    int maxX = Integer.MIN_VALUE, maxY = Integer.MIN_VALUE;
    Map<String, Integer> corners = new HashMap<>();
    
    for (int[] rect : rectangles) {
        totalArea += (long)(rect[2] - rect[0]) * (rect[3] - rect[1]);
        minX = Math.min(minX, rect[0]);
        minY = Math.min(minY, rect[1]);
        maxX = Math.max(maxX, rect[2]);
        maxY = Math.max(maxY, rect[3]);
        
        // 统计每个顶点出现次数
        String[] pts = {
            rect[0] + "," + rect[1],
            rect[0] + "," + rect[3],
            rect[2] + "," + rect[1],
            rect[2] + "," + rect[3]
        };
        for (String p : pts) {
            corners.merge(p, 1, Integer::sum);
        }
    }
    
    // 检查面积
    long boundingArea = (long)(maxX - minX) * (maxY - minY);
    if (totalArea != boundingArea) return false;
    
    // 检查边界顶点
    String[] boundingCorners = {
        minX + "," + minY, minX + "," + maxY,
        maxX + "," + minY, maxX + "," + maxY
    };
    for (String c : boundingCorners) {
        if (corners.getOrDefault(c, 0) != 1) return false;
        corners.remove(c);
    }
    
    // 内部顶点必须出现2次或4次
    for (int count : corners.values()) {
        if (count != 2 && count != 4) return false;
    }
    
    return true;
}

判断条件：

所有子矩形面积之和等于大矩形面积
大矩形的四个角顶点各只出现一次
其他顶点出现 2 次（边上的点）或 4 次（内部的点）

这个方法的精妙之处在于：通过顶点出现次数的模式，间接判断是否存在重叠或间隙。如果存在重叠，某些内部点会出现超过 4 次；如果存在间隙，边界点的出现次数会不符合预期。

时间复杂度：$O(N)$。空间复杂度：$O(N)$。

下落的方块（LeetCode 699）

模拟方块依次下落，返回每次下落后的最大高度。

class SegmentTreeNode {
    int start, end, mid, value, lazy;
    SegmentTreeNode left, right;
    
    SegmentTreeNode(int start, int end) {
        this.start = start;
        this.end = end;
        this.mid = (start + end) >> 1;
    }
}

class SegmentTree {
    SegmentTreeNode root = new SegmentTreeNode(0, (int)1e9);
    
    void pushDown(SegmentTreeNode node) {
        if (node.left == null) node.left = new SegmentTreeNode(node.start, node.mid);
        if (node.right == null) node.right = new SegmentTreeNode(node.mid + 1, node.end);
        if (node.lazy != 0) {
            node.left.value = node.right.value = node.lazy;
            node.left.lazy = node.right.lazy = node.lazy;
            node.lazy = 0;
        }
    }
    
    void update(int l, int r, int val, SegmentTreeNode node) {
        if (l > r || node == null) return;
        if (node.start >= l && node.end <= r) {
            node.value = val;
            node.lazy = val;
            return;
        }
        pushDown(node);
        if (l <= node.mid) update(l, r, val, node.left);
        if (r > node.mid) update(l, r, val, node.right);
        node.value = Math.max(node.left.value, node.right.value);
    }
    
    int query(int l, int r, SegmentTreeNode node) {
        if (l > r || node == null) return 0;
        if (node.start >= l && node.end <= r) return node.value;
        pushDown(node);
        int result = 0;
        if (l <= node.mid) result = Math.max(result, query(l, r, node.left));
        if (r > node.mid) result = Math.max(result, query(l, r, node.right));
        return result;
    }
}

public List<Integer> fallingSquares(int[][] positions) {
    List<Integer> result = new ArrayList<>();
    SegmentTree tree = new SegmentTree();
    int maxHeight = 0;
    
    for (int[] pos : positions) {
        int left = pos[0], size = pos[1];
        int right = left + size - 1;
        int h = tree.query(left, right, tree.root) + size;
        maxHeight = Math.max(maxHeight, h);
        result.add(maxHeight);
        tree.update(left, right, h, tree.root);
    }
    
    return result;
}

算法思路：

对于每个下落的方块，先查询它覆盖区间的当前最大高度
新高度 = 当前最大高度 + 方块边长
更新区间内所有位置的高度为新高度
记录全局最大高度

使用带懒惰传播的线段树，支持区间查询最大值和区间更新。懒惰传播确保更新操作只在必要时下推，避免不必要的递归。

时间复杂度：$O(N \log M)$，其中 $M$ 是坐标范围。空间复杂度：$O(N)$（动态开点线段树只创建必要的节点）。

扫描线算法的统一视角

回顾这些题目，可以发现一个统一的模式：

$$ \text{答案} = \sum_{\text{事件区间}} (\text{区间长度} \times \text{区间状态}) $$

对于一维问题，“区间长度"是时间跨度，“区间状态"是累积计数。

对于二维问题，“区间长度"是 y 方向的覆盖长度，“区间状态"是 x 方向的跨度。

复杂度分析

问题类型	时间复杂度	空间复杂度	核心数据结构
一维区间问题（TreeMap）	$O(N \log N)$	$O(N)$	TreeMap
天际线问题	$O(N \log N)$	$O(N)$	优先队列
矩形面积并集	$O(N \log N)$	$O(N)$	线段树
完美矩形	$O(N)$	$O(N)$	HashMap
下落的方块	$O(N \log N)$	$O(N)$	动态开点线段树

核心技巧总结

事件点提取：找出所有需要处理的"关键时刻”
事件排序：按坐标排序，相同坐标时注意处理顺序
状态维护：选择合适的数据结构维护活动状态
增量计算：只在事件点之间进行计算，避免逐点遍历

扫描线算法的魅力在于：将 $O(N^2)$ 甚至 $O(N^3)$ 的暴力解法，优雅地降维到 $O(N \log N)$。这不仅是技巧，更是一种思维方式——不要试图同时处理所有信息，而是让信息有序地"流过"你的算法。

从 Shamos 和 Hoey 1976 年的开创性工作，到今天 LeetCode 上的各类变体，扫描线算法始终是计算几何和区间处理的基石。掌握它，就掌握了将复杂问题"线性化"的核心思想。

核心思想：事件驱动的线性扫描#

一维扫描线：区间问题的统一框架#

会议室 II（LeetCode 253）#

人口最多的年份（LeetCode 1854）#

拼车问题（LeetCode 1094）#

我的日程安排 II（LeetCode 731）#

删除被覆盖区间（LeetCode 1288）#

员工空闲时间（LeetCode 759）#

区间加法（LeetCode 370）#

二维扫描线：几何问题的降维艺术#

天际线问题（LeetCode 218）#

矩形面积 II（LeetCode 850）#

完美矩形（LeetCode 391）#

下落的方块（LeetCode 699）#

扫描线算法的统一视角#

复杂度分析#

核心技巧总结#

更多精彩内容

最长公共子序列为何能解决十几类LeetCode问题从字符串相似度到DNA比对的动态规划精髓

链表算法为何让无数开发者头疼从指针陷阱到快慢指针的完整LeetCode通关指南

单调队列算法如何在滑动窗口中保持O(n)时间复杂度

背包问题为何成为动态规划的基石从01背包到完全背包的完整LeetCode通关指南

字符串匹配算法为何如此重要从KMP到Z函数的线性时间突围