扫描线

写了几天扫描线了，来说一下心得把，与其说扫描线作为一种算法，更像是一种技巧，因为相对其他算法而言，扫描线的题目没有那么明确的代码模板。这些题的共同点，大致就是都会使用优先队列去维护区间或者“线”。

扫描线的核心在于 将不规则的形状按照水平或者垂直的方式，划分成若干个规则的矩形。

具体的解题思路大致有两种，考虑一道最常见的天际线求解，最简单的做法是，考虑每个矩阵的两条边，一条作为入边一条作为出边，维护当前的最高高度，每次当当前的最高高度不等于前一个最高高度时说明，判断出了一个矩形。这种做法的好处是简单易懂，但是在最开始的时候由于将矩形离散化变成了两条边，所以当我们进行排序和遍历的时候也变成了n =2*n的时间。

public List<List<Integer>> buildingOutline(int[][] buildings) {
        // write your code here
        int len = buildings.length;
        int[][] line = new int[len*2][2];
        for(int i = 0 ; i < len ; i ++){
            line[i][0] = buildings[i][0];line[i][1] = buildings[i][2];
            line[i+len][0] = buildings[i][1];line[i+len][1] = -buildings[i][2];
        }
        Arrays.sort(line,(a,b)->a[0]-b[0]);
        PriorityQueue<Integer>height = new PriorityQueue<>((a,b)->b-a);
        height.add(0);
        List<List<Integer>> ans = new ArrayList<>();
        int []last = new int[]{0,0};
        for(int l = 0 ; l < line.length ;){
            int r = l;
            while(r<line.length&&(line[l][0] == line[r][0])){
                if(height.isEmpty()||line[r][1]>0){
                    height.add(line[r][1]);
                }else{
                    height.remove(-line[r][1]);
                }
                r++;
            }
            int[] cur = new int[]{line[l][0],height.peek()};
            if(last[1]!=0&&(cur[1]!=last[1])){
                ans.add(Arrays.asList(last[0],cur[0],last[1]));
            }
            if(cur[1] != last[1]){
                last = cur;
            }
            l = r;
        }
        return ans;
    }

另一种常见的思路，是直接将矩形进行排序，对每一个矩形，我们考虑当前矩形和下一个矩形，对其中的相交，以及高度状态进行判断并处理，这样细节会难处理一点，但是相对前一种做法，遍历次数和排序都会快一些。

在这两种处理方式中可以看出，扫描线的一个重要议题就是区间合并，无论是二维还是一维，都经常会涉及，而区间合并的实现，主要就通过排序和优先队列来完成

题解

下面记录一点我觉得还不错或者比较特别的题目以及解法。

完美矩形

首先是这道题，也算是经典了，需要找规律一下判断中间的线是有两条相同的，并且对每条线进行区间合并后判断。

矩形面积Ⅱ

然后是这道题，这道题和前面的天际线不同，它将矩形的底边去掉了为0的限制。这题我们也是两种思路，一种是和天际线相同的，考虑两条相邻的线，然后将这两条线上的边进行区间合并，然后进行统计区间，计算面积，最后将所有的区间面积相加。

第二种思路，是考虑两个相邻的矩阵X轴坐标。先对所有的x轴坐标排序去重，然后对所有x轴坐标范围大于前面那一对坐标的方块，进行边的区间合并，最后取最高的进行计算面积。

包含每个查询的最小区间

有时候，还会有一些这种区间查询的题，应该说这种题第一想到的应该是线段树，这种题和前面的二维处理不同，只对一维的线段进行维护，并且根据维护的结构进行扫描处理，就是线性处理。具体和前面的统计区间类似，做一些区间是否重叠包含的判断。

下面贴一点代码吧省的下次也不知道保存到哪了

完美矩阵

矩形面积Ⅱ