当前位置：网站首页>Leetcode0587. 安装栅栏(difficult)

Leetcode0587. 安装栅栏(difficult)

2022-04-23 09:23:00 【笨牛慢耕】

1. 问题描述

2. 初始思路

1. 问题描述

在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。

示例 1:

输入: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]]
输出: [[1,1],[2,0],[4,2],[3,3],[2,4]]
解释:

示例 2:

输入: [[1,2],[2,2],[4,2]]
输出: [[1,2],[2,2],[4,2]]
解释:

即使树都在一条直线上，你也需要先用绳子包围它们。

注意:

所有的树应当被围在一起。你不能剪断绳子来包围树或者把树分成一组以上。
输入的整数在 0 到 100 之间。
花园至少有一棵树。
所有树的坐标都是不同的。
输入的点没有顺序。输出顺序也没有要求。

2. 初始思路

第一感是等价于找一个最小的以点集中的点（即本题中的树）为顶点的凸多边形覆盖所有的顶点的问题。是不是跟线性规划中的单纯形（simplex）方法有点点关联呢？

直观的思路如下：

先找到任意一个最外围的点，比如说横坐标为最大值或者最小值，或者纵坐标为最大值或者最小值的一个点。从这个点出发，按顺时针寻找下一个可能的外围的点。这样逐个找下去直到最后回到起点，形成一个闭环。

这个闭环有可能不是一个凸多边形，所以接下来需要将凹进去的点去掉。

但是如何判断下一个外围的点，如何判断凹进去的点呢？这些视觉上非常容易判断的事情如何以让计算机能够理解的方式用编程语言表达出来呢？

二维空间中的节点如何排“序”呢？

看了看评论区，看到这么一条：我就想问下，这题为什么是“困难”的难度？如果学过了凸包算法，这题不是随便都能做出来么？如果没有学习过凸包算法，自己推，基本不可能吧。

信了。。。不瞎揣摩了，书读的少是硬伤，直接学习官解吧^-^。待学习列表上又多了一项。

3. 方法一: Jarvis 算法

3.1 思路与算法

此题为经典的求凸包的算法，详细的算法原理可以参考凸包(力扣 LeetCode)。常见的凸包算法有多种，在此只描述 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°，两个向量之间构成的旋转方向为逆时针，此时可以知道 r 一定在 $\vec{pq}$ 的左边；叉积等于 0 时，则表示两个向量之间平行，p,q,r 在同一条直线上；叉积小于 0 时，则表示两个向量之间的夹角大于180°，两个向量之间构成的旋转方向为顺时针，此时可以知道 r 一定在 $\vec{pq}$ 的右边。为了找到点 q，定义一个函数 cross() ，这个函数有 3 个参数，分别是当前凸包上的点 p，下一个会加到凸包里的点 q，其他点空间内的任何一个点 r，通过计算向量 $\vec{pq}$ , $\vec{qr}$ 的叉积来判断旋转方向，如果剩余所有的点 r 均满足在向量 $\vec{pq}$ 的左边，则此时我们将 q 加入凸包中。下图说明了这样的关系，点 r 在向量 $\vec{pq}$ 的左边。

从上图中，我们可以观察到点 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-p_y) \end{vmatrix} \\ &= (q_x-p_x) \times (r_y-p_y) - (q_y-p_y) \times (r_x-q_x) \end{aligned}$

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

【复杂度分析】

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

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

         作者：LeetCode-Solution
        链接：https://leetcode-cn.com/problems/erect-the-fence/solution/an-zhuang-zha-lan-by-leetcode-solution-75s3/
        来源：力扣（LeetCode）
        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

感觉这个思路还是很符合直觉的。有足够的时间的话说不定真可以推导出来。

3.2 代码

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]:
                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

执行用时：784 ms, 在所有 Python3 提交中击败了17.02%的用户

内存消耗：15.5 MB, 在所有 Python3 提交中击败了79.79%的用户

leetcode刷题群众真的是藏龙卧虎，直接cv官解也就是这个表现？！

4. 方法二: Graham 算法

4.1 思路与算法

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

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

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

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

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

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

【复杂度分析】

时间复杂度： $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)。

感觉这个解法不如上面的方法一那么直观易懂，但是比方法一快，时间效率与直观易懂是矛盾的吧。摘抄于此供以后参考学习。

4.2 代码

略。

5. 方法三: Andrew 算法

5.1 思路与算法

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

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

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

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