安装栅栏

题目描述

给定一个数组 trees，其中 trees[i] = [xi, yi] 表示树在花园中的位置。

你被要求用最短长度的绳子把整个花园围起来，因为绳子很贵。只有把 所有的树都围起来，花园才围得很好。

返回恰好位于围栏周边的树木的坐标。

示例 1:

输入: points = [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
输出: [[1,1],[2,0],[3,3],[2,4],[4,2]]

示例 2:

输入: points = [[1,2],[2,2],[4,2]]
输出: [[4,2],[2,2],[1,2]]

注意:

  • 1 <= points.length <= 3000
  • points[i].length == 2
  • 0 <= xi, yi <= 100
  • 所有给定的点都是 唯一 的。

方法一：二维凸包（Andrew算法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
    /**
     * 向量相减
     */
    private int[] subtraction(int[] a, int[] b) {
        return new int[]{a[0] - b[0], a[1] - b[1]};
    }

    /**
     * 向量叉乘
     */
    private double crossMultiplication(int[] a, int[] b) {
        return a[0] * b[1] - a[1] * b[0];
    }

    /**
     * 向量 ab 转为 向量 ac 过程中扫过的面积
     */
    private double getArea(int[] a, int[] b, int[] c) {
        return crossMultiplication(subtraction(b, a), subtraction(c, a));
    }

    public int[][] outerTrees(int[][] trees) {
        int n = trees.length, tt = 0;
        int[] stack = new int[n + 10];
        boolean[] visited = new boolean[n + 10];
        stack[++tt] = 0; // 不标记起点
        // 先按x坐标升序，再按y坐标升序
        Arrays.sort(trees, (a, b) -> {
            return a[0] != b[0] ? a[0] - b[0] : a[1] - b[1];
        });
        for (int i = 1; i < n; ++i) {
            int[] c = trees[i];
            while (tt >= 2) {
                int[] a = trees[stack[tt - 1]], b = trees[stack[tt]];
                if (getArea(a, b, c) > 0) visited[stack[tt--]] = false;
                else break;
            }
            stack[++tt] = i;
            visited[i] = true;
        }
        int size = tt;
        for (int i = n - 1; i >= 0 ; --i) {
            if (visited[i]) continue;
            int[] c = trees[i];
            while (tt > size) {
                int[] a = trees[stack[tt - 1]], b = trees[stack[tt]];
                if (getArea(a, b, c) > 0) --tt;
                else break;
            }
            stack[++tt] = i;
        }
        int[][] ans = new int[tt - 1][2];
        for (int i = 1; i < tt; ++i) {
            ans[i - 1] = trees[stack[i]];
        }
        return ans;
    }
}
  • 时间复杂度：排序复杂度为$O(nlogn)$，统计凸包上的点复杂度为 $O(n)$。整体复杂度为 $O(n)$
  • 空间复杂度：$O(n)$