【綜合筆試題】難度 4/5，掃描線運用題

目描述

這是 LeetCode 上的 391. 完美矩形 ，難度為 困難。

Tag : 「掃描線」

給你一個數組 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一個坐标軸平行的矩形。這個矩形的左下頂點是 (xi, yi) ，右上頂點是 (ai, bi) 。

如果所有矩形一起精确覆寫了某個矩形區域，則傳回 true ；否則，傳回 false 。

示例 1：

輸入：rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]

輸出：true

解釋：5      

示例 2：

輸入：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]

輸出：false      

示例 3：

輸入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]

輸出：false      

提示：

掃描線

将每個矩形 看做兩條豎直方向的邊，使用 的形式進行存儲（其中 代表該豎邊的下端點， 代表豎邊的上端點），同時為了區分是矩形的左邊還是右邊，再引入一個辨別位，即以四元組

一個完美矩形的充要條件為：對于完美矩形的每一條非邊緣的豎邊，都「成對」出現（存在兩條完全相同的左邊和右邊重疊在一起）；對于完美矩形的兩條邊緣豎邊，均獨立為一條連續的（不重疊）的豎邊。

如圖（紅色框的為「完美矩形的邊緣豎邊」，綠框的為「完美矩形的非邊緣豎邊」）：

• 綠色：非邊緣豎邊必然有成對的左右兩條完全相同的豎邊重疊在一起；
• 紅色：邊緣豎邊由于隻有單邊，必然不重疊，且連接配接成一條完成的豎邊。

代碼：

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        int n = rectangles.length;
        int[][] rs = new int[n * 2][4];
        for (int i = 0, idx = 0; i < n; i++) {
            int[] re = rectangles[i];
            rs[idx++] = new int[]{re[0], re[1], re[3], 1};
            rs[idx++] = new int[]{re[2], re[1], re[3], -1};
        }
        Arrays.sort(rs, (a,b)->{
            if (a[0] != b[0]) return a[0] - b[0];
            return a[1] - b[1];
        });
        n *= 2;
        // 分别存儲相同的橫坐标下「左邊的線段」和「右邊的線段」 (y1, y2)
        List<int[]> l1 = new ArrayList<>(), l2 = new ArrayList<>();
        for (int l = 0; l < n; ) {
            int r = l;
            l1.clear(); l2.clear();
            // 找到橫坐标相同部分
            while (r < n && rs[r][0] == rs[l][0]) r++;
            for (int i = l; i < r; i++) {
                int[] cur = new int[]{rs[i][1], rs[i][2]};
                List<int[]> list = rs[i][3] == 1 ? l1 : l2;
                if (list.isEmpty()) {
                    list.add(cur);
                } else {
                    int[] prev = list.get(list.size() - 1);
                    if (cur[0] < prev[1]) return false; // 存在重疊
                    else if (cur[0] == prev[1]) prev[1] = cur[1]; // 首尾相連
                    else list.add(cur);
                }
            }
            if (l > 0 && r < n) {
                // 若不是完美矩形的邊緣豎邊，檢查是否成對出現
                if (l1.size() != l2.size()) return false;
                for (int i = 0; i < l1.size(); i++) {
                    if (l1.get(i)[0] == l2.get(i)[0] && l1.get(i)[1] == l2.get(i)[1]) continue;
                    return false;
                }
            } else {
                // 若是完美矩形的邊緣豎邊，檢查是否形成完整一段
                if (l1.size() + l2.size() != 1) return false;
            }
            l = r;
        }
        return true;
    }
}      

• 時間複雜度：将​

  ​rectangles​

  ​​ 劃分成邊集的複雜度為；對邊集進行排序的複雜度為，對排序好的邊集進行周遊檢查，每條邊會被掃描線性次，複雜度為。整體複雜度為
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.391​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。

為了友善各位同學能夠電腦上進行調試和送出代碼，我建立了相關的倉庫：github.com/SharingSour… 。