乐趣区

关于后端:月度刷题计划同款经典计算几何模板题

jiezi

题目形容

这是 LeetCode 上的 587. 装置栅栏 ，难度为 艰难。

Tag :「计算几何」、「凸包」

在一个二维的花园中，有一些用 $(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$ 之间。
  • 花园至多有一棵树。
  • 所有树的坐标都是不同的。
  • 输出的点没有程序。输入程序也没有要求。

二维凸包（Andrew 算法）

这是一道「二维凸包」板子题，须要留神的是网上大多数 Andrew 算法的板子都是有问题的（上面会说）。

Andrew 算法正是用于求解凸包上的所有点（围成所有点的最小周长），其算法逻辑将凸包分为「上凸壳」和「下凸壳」，并别离画出（蓝色分割线将凸包分为两局部）：

根本流程为：

  1. 对所有点进行双关键字排序，先依据 $x$ 坐标排升序，后依据 $y$ 排升序；
    依据 $x$ 排升序的目标，是为了咱们可能往一个方向画出凸包边缘（从左往后画出一半凸壳，从右往左画出另外一半），而将 $y$ 升序目标是能够确保一旦咱们当初从 $a$ 到 $b$ 进行连线，那么 $a$ 到 $b$ 之间的所有点可能确保被围住；
  2. 应用栈来保护所有凸包上的点，或者说凸包上的边，会更为精确，凸包终点元素会在栈中呈现两次（首尾），因而更为精确的形容应该是应用栈保护凸包的所有的边，栈中相邻元素代表凸包上的一条边；

  3. 别离「从前往后」和「从后往前」解决排序好的所有点，来别离画出凸包的两半局部，依据画的是第一局部还是第二局部，保护栈内元的解决逻辑稍有不同：

    a. 画的是凸包的第一局部：

    • 若栈内元素少于 $2$ 个，组成一条线至多须要两个点，阐明此时第一条边都还没画出，间接将元素增加到栈中；

    • 若栈内元素不少于 $2$ 个，思考是否要将栈顶的边删掉（由栈顶前两个元素组成的边）假如栈顶元素为 $b$，栈顶元素的下一位为 $a$，即栈顶存在一条 $a$ 到 $b$ 的边，以后解决到的点为 $c$，此时咱们依据 $ac$ 边是否在 $ab$ 边的时针方向来决定是否要将 $ab$ 边去掉：

      依照上述逻辑解决完所有点，凸包第一局部的点（边）都存在于栈中。

    b. 画的是凸包的第二局部：逻辑同理，惟一须要留神的是，第一局部的凸包边咱们不能删去，假设解决完第一局部凸包，咱们栈内有 $m$ 个元素，咱们须要将上述「栈顶元素不少于 $2$ 个」的逻辑替换为「栈顶元素大于 $m$ 个」，同时已参加到凸包第一局部的点，不能再思考，因而须要额定应用一个 $vis$ 数组来记录应用过的点。

一些细节，为了不便获得栈顶的前两位元素，咱们应用数组实现栈，$stk$ 代表栈容器，$tp$ 代表栈顶元素下标。

正如刚刚讲到，终点会被入栈两次（对应第一条边和最初一条边），因而输入计划时，栈顶和栈底咱们只选其一即可。

代码：

class Solution {int[] subtraction(int[] a, int[] b) { // 向量相减
        return new int[]{a[0] - b[0], a[1] - b[1]};
    }
    double cross(int[] a, int[] b) { // 叉乘
        return a[0] * b[1] - a[1] * b[0];
    }
    double getArea(int[] a, int[] b, int[] c) { // 向量 ab 转为 向量 ac 过程中扫过的面积
        return cross(subtraction(b, a), subtraction(c, a));
    }
    public int[][] outerTrees(int[][] trees) {Arrays.sort(trees, (a, b)->{return a[0] != b[0] ? a[0] - b[0] : a[1] - b[1];
        });
        int n = trees.length, tp = 0;
        int[] stk = new int[n + 10];
        boolean[] vis = new boolean[n + 10];
        stk[++tp] = 0; // 不标记终点
        for (int i = 1; i < n; i++) {int[] c = trees[i];
            while (tp >= 2) {int[] a = trees[stk[tp - 1]], b = trees[stk[tp]];
                if (getArea(a, b, c) > 0) vis[stk[tp--]] = false;
                else break;
            }
            stk[++tp] = i;
            vis[i] = true;
        }
        int size = tp;
        for (int i = n - 1; i >= 0; i--) {if (vis[i]) continue;
            int[] c = trees[i];
            while (tp > size) {int[] a = trees[stk[tp - 1]], b = trees[stk[tp]];
                if (getArea(a, b, c) > 0) tp--;
                // vis[stk[tp--]] = false; // 非必须
                else break;
            }
            stk[++tp] = i;
            // vis[i] = true; // 非必须
        }
        int[][] ans = new int[tp - 1][2];
        for (int i = 1; i < tp; i++) ans[i - 1] = trees[stk[i]];
        return ans;
    }
}
  • 工夫复杂度：排序复杂度为 $O(n\log{n})$，统计凸包上的点复杂度为 $O(n)$。整体复杂度为 $O(n)$
  • 空间复杂度：$O(n)$

网上 Andrew 板子问题

因为我太久没写计算几何了，翻了一下以前在其余 OJ 提交的题，找回本人几年前的板子，好奇心驱使，想看看当初是否有板子上的冲破（通常很难，尤其对于计算几何而言），后果发现网上绝大多数板子都存在重大逻辑谬误：

  1. 最为重大的谬误是，解决凸包第一局部和第二局部，都是应用「栈顶元素不少于 $2$ 个」的逻辑：即便存在 $vis$ 数组也无奈防止该逻辑谬误，在某些数据上，该逻辑 会导致最左边的一些点无奈被围住；
  2. 存在对 vis 数组的谬误了解：vis 的作用仅是为了解决凸包第二局部的时候，不要应用到凸包第一局部的点而已。含意并非是解决过的点，或者以后凸包上的点 ，因而你能够看到我代码正文中写了「不标记终点」和「非必须」，在画第二局部的凸包时，只须要确保第一局部应用的点不参加即可， 反复点问题自身就由遍历所保障，而并非 $vis$ 数组。当然，为了记忆不便，让模板更具备“对称性”，也能够保留在画第二局部凸包的时候，保留对 $vis$ 的保护逻辑，但千万不要搞错了 $vis$ 的含意。

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.587 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

退出移动版