0587-安装栅栏

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

给定一个数组 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
  • 所有给定的点都是 **唯一 **的。

方法一: Jarvis 算法

思路与算法

此题为经典的求凸包的算法，详细的算法原理可以参考「凸包 」。常见的凸包算法有多种，在此只描述 Jarvis 算法、Graham 算法、 Andrew 算法。

Jarvis 算法背后的想法非常简单。首先必须要从凸包上的某一点开始，比如从给定点集中最左边的点开始，例如最左的一点 A_{1。然后选择 A_{2 点使得所有点都在向量 \vec{A_{1}A_{2}的左方或者右方，我们每次选择左方，需要比较所有点以 A_{1 为原点的极坐标角度。然后以 A_{2 为原点，重复这个步骤，依次找到 A_{3},A_{4},\ldots,A_{k。
给定原点 p，如何找到点 q，满足其余的点 r 均在向量 \vec{pq 的左边，我们使用「向量叉积 」来进行判别。我们可以知道两个向量 \vec{pq},\vec{qr 的叉积大于 0 时，则两个向量之间的夹角小于 180 \degree，两个向量之间构成的旋转方向为逆时针，此时可以知道 r 一定在 \vec{pq 的左边；叉积等于 0 时，则表示两个向量之间平行，p,q,r 在同一条直线上；叉积小于 0 时，则表示两个向量之间的夹角大于 180 \degree，两个向量之间构成的旋转方向为顺时针，此时可以知道 r 一定在 \vec{pq 的右边。为了找到点 q，我们使用函数 cross}() ，这个函数有 3 个参数，分别是当前凸包上的点 p，下一个会加到凸包里的点 q，其他点空间内的任何一个点 r，通过计算向量 \vec{pq},\vec{qr 的叉积来判断旋转方向，如果剩余所有的点 r 均满足在向量 \vec{pq 的左边，则此时我们将 q 加入凸包中。
下图说明了这样的关系，点 r 在向量 \vec{pq 的左边。
1
从上图中，我们可以观察到点 p，q 和 r 形成的向量相应地都是逆时针方向，向量 \vec{pq 和 \vec{qr 旋转方向为逆时针，函数 cross}(p,q,r) 返回值大于 0。

\begin{aligned}
cross(p,q,r) &= \vec{pq} \times \vec{qr} \
&= \begin{vmatrix} (q_x-p_x) & (q_y-p_y) \ (r_x-q_x) & (r_y-q_y) \end{vmatrix} \
&= (q_x-p_x) \times (r_y-q_y) - (q_y-p_y) \times (r_x-q_x)
\end{aligned}

我们遍历所有点 r，找到对于点 p 来说逆时针方向最靠外的点 q，把它加入凸包。如果存在 2 个点相对点 p 在同一条线上，我们应当将 q 和 p 同一线段上的边界点都考虑进来，此时需要进行标记，防止重复添加。

通过这样，我们不断将凸包上的点加入，直到回到了开始的点，下面的动图描述了该过程。

<image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png>

代码

[sol1-Python3]
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
class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        def cross(p: List[int], q: List[int], r: List[int]) -> int:
            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])

        n = len(trees)
        if n < 4:
            return trees

        leftMost = 0
        for i, tree in enumerate(trees):
            if tree[0] < trees[leftMost][0] or (tree[0] == trees[leftMost][0] and tree[1] < trees[leftMost][1]):
                leftMost = i

        ans = []
        vis = [False] * n
        p = leftMost
        while True:
            q = (p + 1) % n
            for r, tree in enumerate(trees):
                # // 如果 r 在 pq 的右侧，则 q = r
                if cross(trees[p], trees[q], tree) < 0:
                    q = r
            # 是否存在点 i, 使得 p q i 在同一条直线上
            for i, b in enumerate(vis):
                if not b and i != p and i != q and cross(trees[p], trees[q], trees[i]) == 0:
                    ans.append(trees[i])
                    vis[i] = True
            if not vis[q]:
                ans.append(trees[q])
                vis[q] = True
            p = q
            if p == leftMost:
                break
        return ans
[sol1-C++]
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
class Solution {
public:
    int cross(vector<int> & p, vector<int> & q, vector<int> & r) {
        return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
    }

    vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
        int n = trees.size();
        if (n < 4) {
            return trees;
        }
        int leftMost = 0;
        for (int i = 0; i < n; i++) {
            if (trees[i][0] < trees[leftMost][0] || 
                (trees[i][0] == trees[leftMost][0] && 
                 trees[i][1] < trees[leftMost][1])) {
                leftMost = i;
            }
        }

        vector<vector<int>> res;
        vector<bool> visit(n, false);
        int p = leftMost;
        do {
            int q = (p + 1) % n;
            for (int r = 0; r < n; r++) {
                /* 如果 r 在 pq 的右侧，则 q = r */ 
                if (cross(trees[p], trees[q], trees[r]) < 0) {
                    q = r;
                }
            }
            /* 是否存在点 i, 使得 p 、q 、i 在同一条直线上 */
            for (int i = 0; i < n; i++) {
                if (visit[i] || i == p || i == q) {
                    continue;
                }
                if (cross(trees[p], trees[q], trees[i]) == 0) {
                    res.emplace_back(trees[i]);
                    visit[i] = true;
                }
            }
            if  (!visit[q]) {
                res.emplace_back(trees[q]);
                visit[q] = true;
            }
            p = q;
        } while (p != leftMost);
        return res;
    }
};
[sol1-Java]
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
class Solution {
    public int[][] outerTrees(int[][] trees) {
        int n = trees.length;
        if (n < 4) {
            return trees;
        }
        int leftMost = 0;
        for (int i = 0; i < n; i++) {
            if (trees[i][0] < trees[leftMost][0] || 
                (trees[i][0] == trees[leftMost][0] && 
                 trees[i][1] < trees[leftMost][1])) {
                leftMost = i;
            }
        }

        List<int[]> res = new ArrayList<int[]>();
        boolean[] visit = new boolean[n];
        int p = leftMost;
        do {
            int q = (p + 1) % n;
            for (int r = 0; r < n; r++) {
                /* 如果 r 在 pq 的右侧，则 q = r */ 
                if (cross(trees[p], trees[q], trees[r]) < 0) {
                    q = r;
                }
            }
            /* 是否存在点 i, 使得 p 、q 、i 在同一条直线上 */
            for (int i = 0; i < n; i++) {
                if (visit[i] || i == p || i == q) {
                    continue;
                }
                if (cross(trees[p], trees[q], trees[i]) == 0) {
                    res.add(trees[i]);
                    visit[i] = true;
                }
            }
            if  (!visit[q]) {
                res.add(trees[q]);
                visit[q] = true;
            }
            p = q;
        } while (p != leftMost);
        return res.toArray(new int[][]{});
    }

    public int cross(int[] p, int[] q, int[] r) {
        return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
    }
}
[sol1-C#]
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
public class Solution {
    public int[][] OuterTrees(int[][] trees) {
        int n = trees.Length;
        if (n < 4) {
            return trees;
        }
        int leftMost = 0;
        for (int i = 0; i < n; i++) {
            if (trees[i][0] < trees[leftMost][0] || 
                (trees[i][0] == trees[leftMost][0] && 
                 trees[i][1] < trees[leftMost][1])) {
                leftMost = i;
            }
        }

        IList<int[]> res = new List<int[]>();
        bool[] visit = new bool[n];
        int p = leftMost;
        do {
            int q = (p + 1) % n;
            for (int r = 0; r < n; r++) {
                /* 如果 r 在 pq 的右侧，则 q = r */ 
                if (Cross(trees[p], trees[q], trees[r]) < 0) {
                    q = r;
                }
            }
            /* 是否存在点 i, 使得 p 、q 、i 在同一条直线上 */
            for (int i = 0; i < n; i++) {
                if (visit[i] || i == p || i == q) {
                    continue;
                }
                if (Cross(trees[p], trees[q], trees[i]) == 0) {
                    res.Add(trees[i]);
                    visit[i] = true;
                }
            }
            if  (!visit[q]) {
                res.Add(trees[q]);
                visit[q] = true;
            }
            p = q;
        } while (p != leftMost);
        return res.ToArray();
    }

    public int Cross(int[] p, int[] q, int[] r) {
        return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
    }
}
[sol1-C]
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
60
61
62
63
64
65
66
67
68
int cross(const int * p, const int * q, const int * r) {
    return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
}

int** outerTrees(int** trees, int treesSize, int* treesColSize, int* returnSize, int** returnColumnSizes) {
    int **res = (int **)malloc(sizeof(int *) * treesSize);
    int pos = 0;
    if (treesSize < 4) {
        *returnColumnSizes = (int *)malloc(sizeof(int) * treesSize);
        for (int i = 0; i < treesSize; i++) {
            res[i] = (int *)malloc(sizeof(int) * 2);
            res[i][0] = trees[i][0];
            res[i][1] = trees[i][1];
            (*returnColumnSizes)[i] = 2;
        }
        *returnSize = treesSize;
        return res;
    }
    int leftMost = 0;
    for (int i = 0; i < treesSize; i++) {
        if (trees[i][0] < trees[leftMost][0] || \
            (trees[i][0] == trees[leftMost][0] && \
            trees[i][1] < trees[leftMost][1])) {
            leftMost = i;
        }
    }

    bool *visit = (bool *)malloc(sizeof(bool) * treesSize);
    memset(visit, 0, sizeof(bool) * treesSize);
    int p = leftMost;
    do {
        int q = (p + 1) % treesSize;
        for (int r = 0; r < treesSize; r++) {
            /* 如果 r 在 pq 的右侧，则 q = r */ 
            if (cross(trees[p], trees[q], trees[r]) < 0) {
                q = r;
            }
        }
        /* 是否存在点 i, 使得 p 、q 、i 在同一条直线上 */
        for (int i = 0; i < treesSize; i++) {
            if (visit[i] || i == p || i == q) {
                continue;
            }
            if (cross(trees[p], trees[q], trees[i]) == 0) {
                res[pos] = (int *)malloc(sizeof(int) * 2);
                res[pos][0] = trees[i][0];
                res[pos][1] = trees[i][1];
                pos++;
                visit[i] = true;
            }
        }
        if (!visit[q]) {
            visit[q] = true;
            res[pos] = (int *)malloc(sizeof(int) * 2);
            res[pos][0] = trees[q][0];
            res[pos][1] = trees[q][1];
            pos++;
        }
        p = q;
    } while (p != leftMost);
    *returnSize = pos;
    *returnColumnSizes = (int *)malloc(sizeof(int) * pos);
    for (int i = 0; i < pos; i++) {
        (*returnColumnSizes)[i] = 2;
    }
    free(visit);
    return res;
}
[sol1-JavaScript]
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
var outerTrees = function(trees) {
    const n = trees.length;
    if (n < 4) {
        return trees;
    }
    let leftMost = 0;
    for (let i = 0; i < n; i++) {
        if (trees[i][0] < trees[leftMost][0] || (trees[i][0] == trees[leftMost][0] && trees[i][1] < trees[leftMost][1])) {
            leftMost = i;
        }
    }

    const res = [];
    const visit = new Array(n).fill(0);
    let p = leftMost;
    do {
        let q = (p + 1) % n;
        for (let r = 0; r < n; r++) {
            /* 如果 r 在 pq 的右侧，则 q = r */ 
            if (cross(trees[p], trees[q], trees[r]) < 0) {
                q = r;
            }
        }
        /* 是否存在点 i, 使得 p 、q 、i 在同一条直线上 */
        for (let i = 0; i < n; i++) {
            if (visit[i] || i === p || i === q) {
                continue;
            }
            if (cross(trees[p], trees[q], trees[i]) === 0) {
                res.push(trees[i]);
                visit[i] = true;
            }
        }
        if  (!visit[q]) {
            res.push(trees[q]);
            visit[q] = true;
        }
        p = q;
    } while (p !== leftMost);
    return res;
}

const cross = (p, q, r) => {
    return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
};
[sol1-Golang]
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
func cross(p, q, r []int) int {
    return (q[0]-p[0])*(r[1]-q[1]) - (q[1]-p[1])*(r[0]-q[0])
}

func outerTrees(trees [][]int) (ans [][]int) {
    n := len(trees)
    if n < 4 {
        return trees
    }

    leftMost := 0
    for i, tree := range trees {
        if tree[0] < trees[leftMost][0] || (tree[0] == trees[leftMost][0] && tree[1] < trees[leftMost][1]) {
            leftMost = i
        }
    }

    vis := make([]bool, n)
    p := leftMost
    for {
        q := (p + 1) % n
        for r, tree := range trees {
            // 如果 r 在 pq 的右侧，则 q = r
            if cross(trees[p], trees[q], tree) < 0 {
                q = r
            }
        }
        // 是否存在点 i, 使得 p q i 在同一条直线上
        for i, b := range vis {
            if !b && i != p && i != q && cross(trees[p], trees[q], trees[i]) == 0 {
                ans = append(ans, trees[i])
                vis[i] = true
            }
        }
        if !vis[q] {
            ans = append(ans, trees[q])
            vis[q] = true
        }
        p = q
        if p == leftMost {
            break
        }
    }
    return
}

复杂度分析

  • 时间复杂度：O(n^2)，其中 n 为数组的长度。每次判定一个点 p，同时需要遍历数组所有点，一共最多需要取出 n 个点，因此时间复杂度为 O(n^2)。

  • 空间复杂度：O(n)。需要对每个点进行标记，需要的空间复杂度为 O(n)。

方法二: Graham 算法

思路与算法

这个方法的具体实现为：首先选择一个凸包上的初始点 bottom。我们选择 y 坐标最小的点为起始点，我们可以肯定 bottom 一定在凸包上，将给定点集按照相对的以 bottom 为原点的极角大小进行排序。

这一排序过程大致给了我们在逆时针顺序选点时候的思路。为了将点排序，我们使用上一方法使用过的函数 cross 。极角顺序更小的点排在数组的前面。如果有两个点相对于点 bottom 的极角大小相同，则按照与点 bottom 的距离排序。

我们还需要考虑另一种重要的情况，如果共线的点在凸壳的最后一条边上，我们需要从距离初始点最远的点开始考虑起。所以在将数组排序后，我们从尾开始遍历有序数组并将共线且朝有序数组尾部的点反转顺序，因为这些点是形成凸壳过程中尾部的点，所以在经过了这些处理以后，我们得到了求凸壳时正确的点的顺序。

现在我们从有序数组最开始两个点开始考虑。我们将这条线上的点放入栈中。然后我们从第三个点开始遍历有序数组 trees。如果当前点与栈顶的点相比前一条线是一个「左拐」或者是同一条线段上，我们都将当前点添加到栈顶，表示这个点暂时被添加到凸壳上。

检查左拐或者右拐使用的还是 cross 函数。对于向量 \vec{pq},\vec{qr，计算向量的叉积 cross}(p,q,r) = \vec{pq} \times \vec{qr，如果叉积小于 0，可以知道向量 \vec{pq},\vec{qr 顺时针旋转，则此时向右拐；如果叉积大于 0，可以知道向量 \vec{pq},\vec{qr 逆时针旋转，表示是左拐；如果叉积等于 0，则 p,q,r 在同一条直线上。

如果当前点与上一条线之间的关系是右拐的，说明上一个点不应该被包括在凸壳里，因为它在边界的里面（正如动画中点 4），所以我们将它从栈中弹出并考虑倒数第二条线的方向。重复这一过程，弹栈的操作会一直进行，直到我们当前点在凸壳中出现了右拐。这表示这时凸壳中只包括边界上的点而不包括边界以内的点。在所有点被遍历了一遍以后，栈中的点就是构成凸壳的点。

<image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png>

代码

[sol2-Python3]
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
class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        def cross(p: List[int], q: List[int], r: List[int]) -> int:
            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])

        def distance(p: List[int], q: List[int]) -> int:
            return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1])

        n = len(trees)
        if n < 4:
            return trees

        # 找到 y 最小的点 bottom
        bottom = 0
        for i, tree in enumerate(trees):
            if tree[1] < trees[bottom][1]:
                bottom = i
        trees[bottom], trees[0] = trees[0], trees[bottom]

        # 以 bottom 原点，按照极坐标的角度大小进行排序
        def cmp(a: List[int], b: List[int]) -> int:
            diff = - cross(trees[0], a, b)
            return diff if diff else distance(trees[0], a) - distance(trees[0], b)
        trees[1:] = sorted(trees[1:], key=cmp_to_key(cmp))

        # 对于凸包最后且在同一条直线的元素按照距离从大到小进行排序
        r = n - 1
        while r >= 0 and cross(trees[0], trees[n - 1], trees[r]) == 0:
            r -= 1
        l, h = r + 1, n - 1
        while l < h:
            trees[l], trees[h] = trees[h], trees[l]
            l += 1
            h -= 1

        stack = [0, 1]
        for i in range(2, n):
            # 如果当前元素与栈顶的两个元素构成的向量顺时针旋转，则弹出栈顶元素
            while len(stack) > 1 and cross(trees[stack[-2]], trees[stack[-1]], trees[i]) < 0:
                stack.pop()
            stack.append(i)
        return [trees[i] for i in stack]
[sol2-C++]
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
60
61
62
63
class Solution {
public:
    int cross(const vector<int> & p, const vector<int> & q, const vector<int> & r) {
        return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
    }

    int distance(const vector<int> & p, const vector<int> & q) {
        return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
    }

    vector<vector<int>> outerTrees(vector<vector<int>> &trees) {
        int n = trees.size();
        if (n < 4) {
            return trees;
        }
        int bottom = 0;
        /* 找到 y 最小的点 bottom*/
        for (int i = 0; i < n; i++) {
            if (trees[i][1] < trees[bottom][1]) {
                bottom = i;
            }
        }
        swap(trees[bottom], trees[0]);
        /* 以 bottom 原点，按照极坐标的角度大小进行排序 */
        sort(trees.begin() + 1, trees.end(), [&](const vector<int> & a, const vector<int> & b) {
            int diff = cross(trees[0], a, b);
            if (diff == 0) {
                return distance(trees[0], a) < distance(trees[0], b);
            } else {
                return diff > 0;
            }
        });
        /* 对于凸包最后且在同一条直线的元素按照距离从大到小进行排序 */
        int r = n - 1;
        while (r >= 0 && cross(trees[0], trees[n - 1], trees[r]) == 0) {
            r--;
        }
        for (int l = r + 1, h = n - 1; l < h; l++, h--) {
            swap(trees[l], trees[h]);
        }
        stack<int> st;
        st.emplace(0);
        st.emplace(1);
        for (int i = 2; i < n; i++) {
            int top = st.top();
            st.pop();
            /* 如果当前元素与栈顶的两个元素构成的向量顺时针旋转，则弹出栈顶元素 */
            while (!st.empty() && cross(trees[st.top()], trees[top], trees[i]) < 0) {
                top = st.top();
                st.pop();
            }
            st.emplace(top);
            st.emplace(i);
        }

        vector<vector<int>> res;
        while (!st.empty()) {
            res.emplace_back(trees[st.top()]);
            st.pop();
        }
        return res;
    }
};
[sol2-Java]
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
60
61
62
63
64
65
66
67
68
class Solution {
    public int[][] outerTrees(int[][] trees) {
        int n = trees.length;
        if (n < 4) {
            return trees;
        }
        int bottom = 0;
        /* 找到 y 最小的点 bottom*/
        for (int i = 0; i < n; i++) {
            if (trees[i][1] < trees[bottom][1]) {
                bottom = i;
            }
        }
        swap(trees, bottom, 0);
        /* 以 bottom 原点，按照极坐标的角度大小进行排序 */
        Arrays.sort(trees, 1, n, (a, b) -> {
            int diff = cross(trees[0], a, b);
            if (diff == 0) {
                return distance(trees[0], a) - distance(trees[0], b);
            } else {
                return -diff;
            }
        });
        /* 对于凸包最后且在同一条直线的元素按照距离从大到小进行排序 */
        int r = n - 1;
        while (r >= 0 && cross(trees[0], trees[n - 1], trees[r]) == 0) {
            r--;
        }
        for (int l = r + 1, h = n - 1; l < h; l++, h--) {
            swap(trees, l, h);
        }
        Deque<Integer> stack = new ArrayDeque<Integer>();
        stack.push(0);
        stack.push(1);
        for (int i = 2; i < n; i++) {
            int top = stack.pop();
            /* 如果当前元素与栈顶的两个元素构成的向量顺时针旋转，则弹出栈顶元素 */
            while (!stack.isEmpty() && cross(trees[stack.peek()], trees[top], trees[i]) < 0) {
                top = stack.pop();
            }
            stack.push(top);
            stack.push(i);
        }

        int size = stack.size();
        int[][] res = new int[size][2];
        for (int i = 0; i < size; i++) {
            res[i] = trees[stack.pop()];
        }
        return res;
    }

    public int cross(int[] p, int[] q, int[] r) {
        return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
    }

    public int distance(int[] p, int[] q) {
        return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
    }

    public void swap(int[][] trees, int i, int j) {
        int temp0 = trees[i][0], temp1 = trees[i][1];
        trees[i][0] = trees[j][0];
        trees[i][1] = trees[j][1];
        trees[j][0] = temp0;
        trees[j][1] = temp1;
    }
}
[sol2-C#]
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
60
61
62
63
64
65
66
67
68
public class Solution {
    public int[][] OuterTrees(int[][] trees) {
        int n = trees.Length;
        if (n < 4) {
            return trees;
        }
        int bottom = 0;
        /* 找到 y 最小的点 bottom*/
        for (int i = 0; i < n; i++) {
            if (trees[i][1] < trees[bottom][1]) {
                bottom = i;
            }
        }
        Swap(trees, bottom, 0);
        /* 以 bottom 原点，按照极坐标的角度大小进行排序 */
        Array.Sort(trees, (a, b) => {
            int diff = Cross(trees[0], a, b);
            if (diff == 0) {
                return Distance(trees[0], a) - Distance(trees[0], b);
            } else {
                return -diff;
            }
        });
        /* 对于凸包最后且在同一条直线的元素按照距离从大到小进行排序 */
        int r = n - 1;
        while (r >= 0 && Cross(trees[0], trees[n - 1], trees[r]) == 0) {
            r--;
        }
        for (int l = r + 1, h = n - 1; l < h; l++, h--) {
            Swap(trees, l, h);
        }
        Stack<int> stack = new Stack<int>();
        stack.Push(0);
        stack.Push(1);
        for (int i = 2; i < n; i++) {
            int top = stack.Pop();
            /* 如果当前元素与栈顶的两个元素构成的向量顺时针旋转，则弹出栈顶元素 */
            while (stack.Count > 0 && Cross(trees[stack.Peek()], trees[top], trees[i]) < 0) {
                top = stack.Pop();
            }
            stack.Push(top);
            stack.Push(i);
        }

        int size = stack.Count;
        int[][] res = new int[size][];
        for (int i = 0; i < size; i++) {
            res[i] = trees[stack.Pop()];
        }
        return res;
    }

    public int Cross(int[] p, int[] q, int[] r) {
        return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
    }

    public int Distance(int[] p, int[] q) {
        return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
    }

    public void Swap(int[][] trees, int i, int j) {
        int temp0 = trees[i][0], temp1 = trees[i][1];
        trees[i][0] = trees[j][0];
        trees[i][1] = trees[j][1];
        trees[j][0] = temp0;
        trees[j][1] = temp1;
    }
}
[sol2-C]
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
static int cross(const int * p, const int * q, const int * r) {
    return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
}

static int distance(const int * p, const int * q) {
    return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
}

static int * p = NULL;

static int cmp(const void * pa, const void * pb) {
    int *a = *((int **)pa);
    int *b = *((int **)pb);
    int diff = cross(p, a, b);
    if (diff == 0) {
        return distance(p, a) - distance(p, b);
    } else {
        return -diff;
    } 
}

static void swap(int * pa, int * pb) {
    int c = pa[0];
    pa[0] = pb[0];
    pb[0] = c;
    c = pa[1];
    pa[1] = pb[1];
    pb[1] = c;
}

int** outerTrees(int** trees, int treesSize, int* treesColSize, int* returnSize, int** returnColumnSizes) {
    int **res = (int **)malloc(sizeof(int *) * treesSize);
    int pos = 0;
    if (treesSize < 4) {
        *returnColumnSizes = (int *)malloc(sizeof(int) * treesSize);
        for (int i = 0; i < treesSize; i++) {
            res[i] = (int *)malloc(sizeof(int) * 2);
            res[i][0] = trees[i][0];
            res[i][1] = trees[i][1];
            (*returnColumnSizes)[i] = 2;
        }
        *returnSize = treesSize;
        return res;
    }
    int bottom = 0;
    /* 找到 y 最小的点 bottom*/
    for (int i = 0; i < treesSize; i++) {
        if (trees[i][1] < trees[bottom][1] || 
            (trees[i][1] == trees[bottom][1] && 
             trees[i][0] < trees[bottom][0])) {
            bottom = i;
        }
    }
    swap(trees[bottom], trees[0]);
    p = trees[0];
    /* 以 bottom 原点，按照极坐标的角度大小进行排序 */
    qsort(trees + 1, treesSize - 1, sizeof(int *), cmp);
    /* 对于凸包最后且在同一条直线的元素按照距离从大到小进行排序 */
    int r = treesSize - 1;
    while (r >= 0 && cross(trees[0], trees[treesSize - 1], trees[r]) == 0) {
        r--;
    }
    for (int l = r + 1, h = treesSize - 1; l < h; l++, h--) {
        swap(trees[l], trees[h]);
    }
    int * stack = (int *)malloc(sizeof(int) * treesSize);
    int top = 0;
    stack[top++] = 0;
    stack[top++] = 1;
    for (int i = 2; i < treesSize; i++) {
        /* 如果当前元素与栈顶的两个元素构成的向量顺时针旋转，则弹出栈顶元素 */
        while (top > 1 && cross(trees[stack[top - 2]], trees[stack[top - 1]], trees[i]) < 0) {
            top--;
        }
        stack[top++] = i;
    }
    while (top > 0) {
        res[pos] = (int *)malloc(sizeof(int) * 2);
        memcpy(res[pos], trees[stack[top - 1]], sizeof(int) * 2);
        pos++;
        top--;
    }
    *returnSize = pos;
    *returnColumnSizes = (int *)malloc(sizeof(int) * pos);
    for (int i = 0; i < pos; i++) {
        (*returnColumnSizes)[i] = 2;
    }
    free(stack);
    return res;
}
[sol2-JavaScript]
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
var outerTrees = function(trees) {
    const n = trees.length;
    if (n < 4) {
        return trees;
    }
    let bottom = 0;
    /* 找到 y 最小的点 bottom*/
    for (let i = 0; i < n; i++) {
        if (trees[i][1] < trees[bottom][1]) {
            bottom = i;
        }
    }
    trees = swap(trees, bottom, 0);
    /* 以 bottom 原点，按照极坐标的角度大小进行排序 */
    trees.sort((a, b) => {
        let diff = cross(trees[0], a, b);
        return diff === 0 ? distance(trees[0], a) - distance(trees[0], b) : diff > 0 ? 1 : -1;
    });
    /* 对于凸包最后且在同一条直线的元素按照距离从大到小进行排序 */
    let r = n - 1;
    while (r >= 0 && cross(trees[0], trees[n - 1], trees[r]) === 0) {
        r--;
    }
    for (let l = r + 1, h = n - 1; l < h; l++, h--) {
        trees = swap(trees, l, h);
    }
    const stack = [trees[0], trees[1]];
    for (let i = 2; i < n; i++) {
        let top = stack.pop();
        /* 如果当前元素与栈顶的两个元素构成的向量顺时针旋转，则弹出栈顶元素 */
        while (cross(stack[stack.length - 1], top, trees[i]) > 0) {
            top = stack.pop();
        }
        stack.push(top);
        stack.push(trees[i]);
    }
    return stack;
}

const cross = (p, q, r) => {
    return (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1]);
}

const distance = (p, q) => {
    return (p[0] - q[0]) * (p[0] - q[0]) + (p[1] - q[1]) * (p[1] - q[1]);
}

const swap = (trees, i, j) => {
    let temp0 = trees[i][0], temp1 = trees[i][1];
    trees[i][0] = trees[j][0];
    trees[i][1] = trees[j][1];
    trees[j][0] = temp0;
    trees[j][1] = temp1;
    return trees;
}
[sol2-Golang]
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
func cross(p, q, r []int) int {
    return (q[0]-p[0])*(r[1]-q[1]) - (q[1]-p[1])*(r[0]-q[0])
}

func distance(p, q []int) int {
    return (p[0]-q[0])*(p[0]-q[0]) + (p[1]-q[1])*(p[1]-q[1])
}

func outerTrees(trees [][]int) [][]int {
    n := len(trees)
    if n < 4 {
        return trees
    }

    // 找到 y 最小的点 bottom
    bottom := 0
    for i, tree := range trees {
        if tree[1] < trees[bottom][1] {
            bottom = i
        }
    }
    trees[bottom], trees[0] = trees[0], trees[bottom]

    // 以 bottom 原点，按照极坐标的角度大小进行排序
    tr := trees[1:]
    sort.Slice(tr, func(i, j int) bool {
        a, b := tr[i], tr[j]
        diff := cross(trees[0], a, b)
        return diff > 0 || diff == 0 && distance(trees[0], a) < distance(trees[0], b)
    })

    // 对于凸包最后且在同一条直线的元素按照距离从大到小进行排序
    r := n - 1
    for r >= 0 && cross(trees[0], trees[n-1], trees[r]) == 0 {
        r--
    }
    for l, h := r+1, n-1; l < h; l++ {
        trees[l], trees[h] = trees[h], trees[l]
        h--
    }

    st := []int{0, 1}
    for i := 2; i < n; i++ {
        // 如果当前元素与栈顶的两个元素构成的向量顺时针旋转，则弹出栈顶元素
        for len(st) > 1 && cross(trees[st[len(st)-2]], trees[st[len(st)-1]], trees[i]) < 0 {
            st = st[:len(st)-1]
        }
        st = append(st, i)
    }

    ans := make([][]int, len(st))
    for i, idx := range st {
        ans[i] = trees[idx]
    }
    return ans
}

复杂度分析

  • 时间复杂度：O(n \log n)，其中 n 为数组的长度。首先需要对数组进行排序，时间复杂度为 O(n \log n)，每次添加栈中添加元素后，判断新加入的元素是否在凸包上，因此每个元素都可能进行入栈与出栈一次，最多需要的时间复杂度为 O(2n)，因此总的时间复杂度为 O(n \log n)。

  • 空间复杂度：O(n)，其中 n 为数组的长度。首先该解法需要快速排序，需要的栈空间为 O(\log n)，需要栈来保存当前已经判别的元素，栈中最多有 n 个元素，所需要的空间为 O(n)，因此总的空间复杂度为 O(n)。

方法三: Andrew 算法

思路与算法

Andrew 使用单调链算法，该算法与 Graham 扫描算分类似。它们主要的不同点在于凸壳上点的顺序。与 Graham 扫描算法按照点计较顺序排序不同，我们按照点的 x 坐标排序，如果两个点又相同的 x 坐标，那么就按照它们的 y 坐标排序。显然排序后的最大值与最小值一定在凸包上，而且因为是凸多边形，我们如果从一个点出发逆时针走，轨迹总是「左拐」的，一旦出现右拐，就说明这一段不在凸包上，因此我们可以用一个单调栈来维护上下凸壳。

仔细观察可以发现，最小值与最大值一定位于凸包的最左边与最右边，从左向右看，我们将凸壳考虑成 2 个子边界组成：上凸壳和下凸壳。下凸壳一定是从最小值一直「左拐」直到最大值，上凸壳一定是从最大值「左拐」到最小值，因此我们首先升序枚举求出下凸壳，然后降序求出上凸壳。
我们首先将最初始的两个点添加到凸壳中，然后遍历排好序的 trees 数组。对于每个新的点，我们检查当前点是否在最后两个点的逆时针方向上，轨迹是否是左拐。如果是的话，当前点直接被压入凸壳 hull 中，cross 返回的结果为正数；如果不是的话，cross 返回的结果为负数，我们可以知道栈顶的元素在凸壳里面而不是凸壳边上。我们继续从 hull 中弹出元素直到当前点相对于栈顶的两个点的逆时针方向上。

这个方法中，我们不需要显式地考虑共线的点，因为这些点已经按照 x 坐标排好了序。所以如果有共线的点，它们已经被隐式地按正确顺序考虑了。通过这样，我们会一直遍历到 x 坐标最大的点为止。但是凸壳还没有完全求解出来。目前求解出来的部分只包括凸壳的下半部分。现在我们需要求出凸壳的上半部分。

我们继续找下一个逆时针的点并将不在边界上的点从栈中弹出，但这次我们遍历的顺序是按照 x 坐标从大到小，我们只需要从后往前遍历有序数组 trees 即可。我们将新的上凸壳的值添加到之前的 hull 数组中。最后 hull 数组返回了我们需要的边界上的点。需要注意的是，由于我们需要检测上凸壳最后加入的点是否合法，此时需要再次插入最左边的点 textit{hull}[0] 进行判别。

下面的动图展示了这一过程。

<image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png,image.png>

代码

[sol3-Python3]
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
class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        def cross(p: List[int], q: List[int], r: List[int]) -> int:
            return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0])

        n = len(trees)
        if n < 4:
            return trees

        # 按照 x 从小到大排序，如果 x 相同，则按照 y 从小到大排序
        trees.sort()

        hull = [0]  # hull[0] 需要入栈两次，不标记
        used = [False] * n
        # 求凸包的下半部分
        for i in range(1, n):
            while len(hull) > 1 and cross(trees[hull[-2]], trees[hull[-1]], trees[i]) < 0:
                used[hull.pop()] = False
            used[i] = True
            hull.append(i)
        # 求凸包的上半部分
        m = len(hull)
        for i in range(n - 2, -1, -1):
            if not used[i]:
                while len(hull) > m and cross(trees[hull[-2]], trees[hull[-1]], trees[i]) < 0:
                    used[hull.pop()] = False
                used[i] = True
                hull.append(i)
        # hull[0] 同时参与凸包的上半部分检测，因此需去掉重复的 hull[0]
        hull.pop()

        return [trees[i] for i in hull]
[sol3-C++]
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
class Solution {
public:
    int cross(const vector<int> & p, const vector<int> & q, const vector<int> & r) {
        return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
    }

    vector<vector<int>> outerTrees(vector<vector<int>>& trees) {
        int n = trees.size();
        if (n < 4) {
            return trees;
        }
        /* 按照 x 大小进行排序，如果 x 相同，则按照 y 的大小进行排序 */
        sort(trees.begin(), trees.end(), [](const vector<int> & a, const vector<int> & b) {
            if (a[0] == b[0]) {
                return a[1] < b[1];
            }
            return a[0] < b[0];
        });
        vector<int> hull;
        vector<bool> used(n, false);
        /* hull[0] 需要入栈两次，不进行标记 */
        hull.emplace_back(0);
        /* 求出凸包的下半部分 */
        for (int i = 1; i < n; i++) {
            while (hull.size() > 1 && cross(trees[hull[hull.size() - 2]], trees[hull.back()], trees[i]) < 0) {
                used[hull.back()] = false;
                hull.pop_back();
            }
            used[i] = true;
            hull.emplace_back(i);
        }
        int m = hull.size();
        /* 求出凸包的上半部分 */
        for (int i = n - 2; i >= 0; i--) {
            if (!used[i]) {
                while (hull.size() > m && cross(trees[hull[hull.size() - 2]], trees[hull.back()], trees[i]) < 0) {
                    used[hull.back()] = false;
                    hull.pop_back();
                }
                used[i] = true;
                hull.emplace_back(i);
            }
        }
        /* hull[0] 同时参与凸包的上半部分检测，因此需去掉重复的 hull[0] */
        hull.pop_back();
        vector<vector<int>> res;
        for(auto & v : hull) {
            res.emplace_back(trees[v]);
        }
        return res;
    }
};
[sol3-Java]
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
class Solution {
    public int[][] outerTrees(int[][] trees) {
        int n = trees.length;
        if (n < 4) {
            return trees;
        }
        /* 按照 x 大小进行排序，如果 x 相同，则按照 y 的大小进行排序 */
        Arrays.sort(trees, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });
        List<Integer> hull = new ArrayList<Integer>();
        boolean[] used = new boolean[n];
        /* hull[0] 需要入栈两次，不进行标记 */
        hull.add(0);
        /* 求出凸包的下半部分 */
        for (int i = 1; i < n; i++) {
            while (hull.size() > 1 && cross(trees[hull.get(hull.size() - 2)], trees[hull.get(hull.size() - 1)], trees[i]) < 0) {
                used[hull.get(hull.size() - 1)] = false;
                hull.remove(hull.size() - 1);
            }
            used[i] = true;
            hull.add(i);
        }
        int m = hull.size();
        /* 求出凸包的上半部分 */
        for (int i = n - 2; i >= 0; i--) {
            if (!used[i]) {
                while (hull.size() > m && cross(trees[hull.get(hull.size() - 2)], trees[hull.get(hull.size() - 1)], trees[i]) < 0) {
                    used[hull.get(hull.size() - 1)] = false;
                    hull.remove(hull.size() - 1);
                }
                used[i] = true;
                hull.add(i);
            }
        }
        /* hull[0] 同时参与凸包的上半部分检测，因此需去掉重复的 hull[0] */
        hull.remove(hull.size() - 1);
        int size = hull.size();
        int[][] res = new int[size][2];
        for (int i = 0; i < size; i++) {
            res[i] = trees[hull.get(i)];
        }
        return res;
    }

    public int cross(int[] p, int[] q, int[] r) {
        return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
    }
}
[sol3-C#]
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
public class Solution {
    public int[][] OuterTrees(int[][] trees) {
        int n = trees.Length;
        if (n < 4) {
            return trees;
        }
        /* 按照 x 大小进行排序，如果 x 相同，则按照 y 的大小进行排序 */
        Array.Sort(trees, (a, b) => {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });
        IList<int> hull = new List<int>();
        bool[] used = new bool[n];
        /* hull[0] 需要入栈两次，不进行标记 */
        hull.Add(0);
        /* 求出凸包的下半部分 */
        for (int i = 1; i < n; i++) {
            while (hull.Count > 1 && Cross(trees[hull[hull.Count - 2]], trees[hull[hull.Count - 1]], trees[i]) < 0) {
                used[hull[hull.Count - 1]] = false;
                hull.RemoveAt(hull.Count - 1);
            }
            used[i] = true;
            hull.Add(i);
        }
        int m = hull.Count;
        /* 求出凸包的上半部分 */
        for (int i = n - 2; i >= 0; i--) {
            if (!used[i]) {
                while (hull.Count > m && Cross(trees[hull[hull.Count - 2]], trees[hull[hull.Count - 1]], trees[i]) < 0) {
                    used[hull[hull.Count - 1]] = false;
                    hull.RemoveAt(hull.Count - 1);
                }
                used[i] = true;
                hull.Add(i);
            }
        }
        /* hull[0] 同时参与凸包的上半部分检测，因此需去掉重复的 hull[0] */
        hull.RemoveAt(hull.Count - 1);
        int size = hull.Count;
        int[][] res = new int[size][];
        for (int i = 0; i < size; i++) {
            res[i] = trees[hull[i]];
        }
        return res;
    }

    public int Cross(int[] p, int[] q, int[] r) {
        return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
    }
}
[sol3-C]
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
60
61
62
63
64
65
66
67
68
static int cross(const int * p, const int * q, const int * r) {
    return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
}

static int cmp(const void * pa, const void * pb) {
    int *a = *((int **)pa);
    int *b = *((int **)pb);
    if (a[0] == b[0]) {
        return a[1] - b[1];
    }
    return a[0] - b[0];
}

int** outerTrees(int** trees, int treesSize, int* treesColSize, int* returnSize, int** returnColumnSizes) {
    int **res = (int **)malloc(sizeof(int *) * treesSize);
    int pos = 0;
    if (treesSize < 4) {
        *returnColumnSizes = (int *)malloc(sizeof(int) * treesSize);
        for (int i = 0; i < treesSize; i++) {
            res[i] = (int *)malloc(sizeof(int) * 2);
            res[i][0] = trees[i][0];
            res[i][1] = trees[i][1];
            (*returnColumnSizes)[i] = 2;
        }
        *returnSize = treesSize;
        return res;
    }
    
    qsort(trees, treesSize, sizeof(int *), cmp);
    int * hull = (int *)malloc(sizeof(int) * (treesSize + 1));
    int * used = (int *)malloc(sizeof(int) * treesSize);
    memset(used, 0, sizeof(int) * treesSize);
    /* hull[0] 需要入栈两次，不进行标记 */
    hull[pos++] = 0;
    /* 求出凸包的下半部分 */
    for (int i = 1; i < treesSize; i++) {
        while (pos > 1 && cross(trees[hull[pos - 2]], trees[hull[pos - 1]], trees[i]) < 0) {
            used[hull[pos - 1]] = false;
            pos--;
        }
        used[i] = true;
        hull[pos++] = i;
    }
    int m = pos;
    /* 求出凸包的上半部分 */
    for (int i = treesSize - 2; i >= 0; i--) {
        if (!used[i]) {
            while (pos > m && cross(trees[hull[pos - 2]], trees[hull[pos - 1]], trees[i]) < 0) {
                used[hull[pos - 1]] = false;
                pos--;
            }
            used[i] = true;
            hull[pos++] = i;
        }
    }
    /* hull[0] 同时参与凸包的上半部分检测，因此需去掉重复的 hull[0] */
    pos--;
    *returnSize = pos;
    *returnColumnSizes = (int *)malloc(sizeof(int) * pos);
    for (int i = 0; i < pos; i++) {
        (*returnColumnSizes)[i] = 2;
        res[i] = (int *)malloc(sizeof(int) * 2);
        memcpy(res[i], trees[hull[i]], sizeof(int) * 2);
    }
    free(used);
    free(hull);
    return res;
}
[sol3-JavaScript]
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
var outerTrees = function(trees) {
    const n = trees.length;
    if (n < 4) {
        return trees;
    }
    /* 按照 x 大小进行排序，如果 x 相同，则按照 y 的大小进行排序 */
    trees.sort((a, b) => {
        if (a[0] === b[0]) {
            return a[1] - b[1];
        }
        return a[0] - b[0];
    });
    const hull = [];
    const used = new Array(n).fill(0);
    /* hull[0] 需要入栈两次，不进行标记 */
    hull.push(0);
    /* 求出凸包的下半部分 */
    for (let i = 1; i < n; i++) {
        while (hull.length > 1 && cross(trees[hull[hull.length - 2]], trees[hull[hull.length - 1]], trees[i]) < 0) {
            used[hull[hull.length - 1]] = false;
            hull.pop();
        }
        used[i] = true;
        hull.push(i);
    }
    const m = hull.length;
    /* 求出凸包的上半部分 */
    for (let i = n - 2; i >= 0; i--) {
        if (!used[i]) {
            while (hull.length > m && cross(trees[hull[hull.length - 2]], trees[hull[hull.length - 1]], trees[i]) < 0) {
                used[hull[hull.length - 1]] = false;
                hull.pop();
            }
            used[i] = true;
            hull.push(i);
        }
    }
    /* hull[0] 同时参与凸包的上半部分检测，因此需去掉重复的 hull[0] */
    hull.pop();
    const size = hull.length;
    const res = new Array(size).fill(0).map(() => new Array(2).fill(0));
    for (let i = 0; i < size; i++) {
        res[i] = trees[hull[i]];
    }
    return res;
}

const cross = (p, q, r) => {
    return (q[0] - p[0]) * (r[1] - q[1]) - (q[1] - p[1]) * (r[0] - q[0]);
}
[sol3-Golang]
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
func cross(p, q, r []int) int {
    return (q[0]-p[0])*(r[1]-q[1]) - (q[1]-p[1])*(r[0]-q[0])
}

func outerTrees(trees [][]int) [][]int {
    n := len(trees)
    if n < 4 {
        return trees
    }

    // 按照 x 从小到大排序，如果 x 相同，则按照 y 从小到大排序
    sort.Slice(trees, func(i, j int) bool { a, b := trees[i], trees[j]; return a[0] < b[0] || a[0] == b[0] && a[1] < b[1] })

    hull := []int{0} // hull[0] 需要入栈两次，不标记
    used := make([]bool, n)
    // 求凸包的下半部分
    for i := 1; i < n; i++ {
        for len(hull) > 1 && cross(trees[hull[len(hull)-2]], trees[hull[len(hull)-1]], trees[i]) < 0 {
            used[hull[len(hull)-1]] = false
            hull = hull[:len(hull)-1]
        }
        used[i] = true
        hull = append(hull, i)
    }
    // 求凸包的上半部分
    m := len(hull)
    for i := n - 2; i >= 0; i-- {
        if !used[i] {
            for len(hull) > m && cross(trees[hull[len(hull)-2]], trees[hull[len(hull)-1]], trees[i]) < 0 {
                used[hull[len(hull)-1]] = false
                hull = hull[:len(hull)-1]
            }
            used[i] = true
            hull = append(hull, i)
        }
    }
    // hull[0] 同时参与凸包的上半部分检测，因此需去掉重复的 hull[0]
    hull = hull[:len(hull)-1]

    ans := make([][]int, len(hull))
    for i, idx := range hull {
        ans[i] = trees[idx]
    }
    return ans
}

复杂度分析

  • 时间复杂度：O(n \log n)，其中 n 为数组的长度。首先需要对数组进行排序，时间复杂度为 O(n \log n)，每次添加栈中添加元素后，判断新加入的元素是否在凸包上，因此每个元素都可能进行入栈与出栈一次，最多需要的时间复杂度为 O(2n)，因此总的时间复杂度为 O(n \log n)。

  • 空间复杂度：O(n)，其中 n 为数组的长度。首先该解法需要快速排序，需要的栈空间为 O(\log n)，用来标记元素是否存在重复访问的空间复杂度为 O(n)，需要栈来保存当前判别的凸包上的元素，栈中最多有 n 个元素，所需要的空间为 O(n)，因此总的空间复杂度为 O(n)。

 Comments
On this page
0587-安装栅栏