0587：安装栅栏（★★）

2015-01-01 约 284 字预计阅读 1 分钟次阅读

力扣第 587 题

题目

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

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

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

示例 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 <= x_i, y_i <= 100
所有给定的点都是唯一的。

相似问题：

分析

经典的凸包问题，常用 Andrew 算法。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution:
    def outerTrees(self, trees: List[List[int]]) -> List[List[int]]:
        def cal(a,b,c):
            return (b[0]-a[0])*(c[1]-a[1])-(b[1]-a[1])*(c[0]-a[0])
        
        def get(A):
            sk = []
            for a in A:
                while len(sk)>=2 and cal(sk[-2],sk[-1],a)<0:
                    sk.pop()
                sk.append(tuple(a))
            return sk

        trees.sort()
        res = get(trees)
        vis = set(res)
        for a in get(trees[::-1])[1:]:
            if a in vis:
                break
            res.append(a)
        return res

71 ms

目录

0587：安装栅栏（★★）

题目

分析

解答