1. Leetcode算法笔记 - 凸包问题，Andrew解法

【算法笔记】这块内容只是做个人笔记，不用于教学和题解或题解目的，因此不索引也不评论，请谨慎参考，题解建议阅读官方题解或宫水三叶等优质作者发布的题解，这话仅出现一次。

昨天Leetcode的题目是 587. 安装栅栏 ，学习了凸包问题，就稍微以自己的理解，加上三叶姐写的题解（下面说 题解）的代码加以自己的理解来写个笔记。

(English version translate by GPT-3.5)

原题

原文： Leetcode 4.23 每日一题 537. 安装栅栏

在一个二维的花园中，有一些用 (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]]

理解Andrew算法思想

这题难度如果会凸包算法的情况下，那会简单很多很多，所以这个我就逼自己一定要看懂。

1. 题解是使用Andrew算法来解决这个问题，Andrew算法分为2部分，先从左到右，找到下半部分的凸点，然后再从右到左，找到上半部分的凸点，最后合并2个结果，就是最终答案。

2. 先找到上半凸壳（红色）

   

3. 然后找到下半凸壳（蓝色）

   

深入理解

既然了解了基本的思想，接着就是如何实现它了。

1. 首先就是找到最左边的点，即找到离原点最最近的一个点，所以这里可以先将（x，y）坐标先按照x排序，然后按照y排序，这样【0】号位就是离原点最近的坐标。
2. 使用一个stack数组变量来维护每一个边（一条边至少2个点），以及维护一个记录栈顶位置的int变量，同时定义一个visited数组来记录被访问过的节点，当然stack里面存的是一个个（x，y）的点，每相邻的2个点是一条边
3. 然后从【1】位开始（因为0位就是起点x，y），先取得一个点C，然后持续判断下栈内元素是不是2个（因为2个才能组成一条边），如果没有，直接将点C入栈，如果栈内元素小于大于等于2个，则将最后2个栈元素取出来，设A点和B点，加上新的点C形成2条边AB,AC，然后对其做向量叉积（2个点向量计算方法是B点坐标与A点相减 (Bx - Ax, By - Ay)），这样如果叉积结果大于0，表示AB需要旋转顺时针才能与AC重叠，这就表示C点比B点更靠近外面，此时需要将B点出栈（此时栈顶要减去1）并推入C点，此时栈内最后2个元素就变成了A点和C点（此时的C点会变成上面的B点）
4. 按上述规则，直到遍历到最右边的点，此时栈中就存下了凸壳下半部分的点
5. 然后从右到左，并从有到左再次按照上面这条逻辑判断，注意此时要持续判断栈内元素是否大于下凸壳的总大小（因为下凸壳已有的数据不能被移除掉），这样就找到了上凸壳的点
6. 最后，答案就是栈顶 - 1的值，因为栈顶长度最后一个对应的值就是原点0点的值。
7. 输出答案，结束。

逻辑代码实现

一步步按上面逻辑实现一下，输入的数据是

[2,0], [1,1], [2,1], [2,2], [4,2], [3,3], [2,4]

1. 首先就是找到最左边的点，先把上述进行排序，先按x升序，如果x一致按照y升序

   // 排序数组，按X升序，如果X一致再按Y升序
   Arrays.sort(trees, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

2. 然后一个stack数组变量维护每一个边，一个int变量记录栈顶位置，以及一个visited数组来记录被访问的点

   // 定义stack来记录点（边）
   int[] stack = new int[trees.length + 5];
   // 记录栈顶的位置
   int peek = 0;
   // 记录被访问过的节点
   boolean[] visited = new boolean[trees.length + 5];

3. 然后从1位开始，取得一个点c

   for (int i = 1; i < trees.length; i++) {
   	// 从第一位开始，因为stack[0]就是对应tree[0]的值，取得一个点c
   	int[] pointC = trees[i];
   }

4. 然后判断当前栈顶是否有2个点，然后循环判断这个点c与栈里面倒数2个点的的关系，即点Astack[peek- 1]和点Bstack[peek]，与点A和点C（新取到的点），之间的叉积是否大于0，如果大于0，表示边AC比边AB更加靠外，此时将B点推出，然后再进行判断，此时由于点B出栈，则点A变成点B，而点A前面一个点变成新的点A，再次按照上述逻辑进行判断。

   // 判断当前栈顶是否有2个点，如果栈顶位置小于2，则此时栈里面的点构不成边，跳出
   while(peek >= 2) {
       // 然后然后循环判断这个点c与栈里面倒数1，2个点的的关系，即点A`stack[peek - 1]`和点B`stack[peek]`的关系
       int[] pointA = trees[stack[peek - 1]];
       int[] pointB = trees[stack[peek]];
       // 与点A和点C（新取到的点），之间的叉积是否大于0，
       if(getArea(pointA, pointB, pointC) > 0) {
           // 如果大于0，表示边AC比边AB更加靠外，此时将B点推出
           // 先将当前栈顶peek值对应的tree坐标取出，因为stack【i】里面存着第i个元素的点位
           int currentStack = stack[peek];
           // 然后将当前标记为未访问过
           visited[currentStack] = false;
           // 然后栈顶回退一位
           peek--;
           // 然后再进行判断，此时由于点B出栈，则点A即trees[stack[peek - 1]]变成点B，而点A前面一个点peek -- 后的trees[stack[peek - 1]]变成新的点A，再次按照上述逻辑进行判断。
       } else {
           // 否则，则跳出判断
           break;
       }
   }

5. 此时，stack【0 - peek】的值就是下凸壳的点，接着再次循环，按同样逻辑判断上凸壳

   // 这里的size指的是上凸点的长度
   int size = peek;
   // 接着，从右往左，再次判断，这里生成的是下半部分
   for (int i = trees.length - 1; i >= 0; i--) {
       if(visited[i]) {
           continue;
       }
       // 老样子，获得一个熟悉的点C
       int[] pointC = trees[i];
       // 这里不能大于2了，因为stack已经保存了n个上凸壳的位置，所以peek大概率会大于2，如果按照peek >= 2来算，
       // 那么下凸壳有点与原有的2个点更靠外，就会删掉上凸壳的点位
       // 所以对于第一次进入这个方法循环，此时点A就是上凸壳最后一个点，而点B就是下凸壳右边的第一个点
       while(peek > size) {
           // 一样取得2个熟悉的点
           int[] pointA = trees[stack[peek - 1]];
           int[] pointB = trees[stack[peek]];
           // 与点A和点C（新取到的点），之间的叉积是否大于0，
           if(getArea(pointA, pointB, pointC) > 0) {
               // 如果是，那么peek回退一层，和上面做法一样
               int currentStack = stack[peek];
               visited[currentStack] = false;
               peek--;
           } else {
               // 否则，则跳出判断
               break;
           }
       }
       // 然后将点C推入
       peek++;
       stack[peek] = i;
       visited[i] = true;
   }

6. 最后输出得到结果

   // 最后结果是peek减去1，因为最后一位是原点
   int[][] resultPoint = new int[peek - 1][2];
   // 写入结果
   for (int i = 1; i < peek; i++) {
       // peek是从1开始的，所以这里要减去1
       resultPoint[i - 1] = trees[stack[i]];
   }
   // 结束
   return resultPoint;

模拟过程

完整代码

class Solution {
    public int[][] outerTrees(int[][] trees) {
        // 排序数组，按X升序，如果X一致再按Y升序
        Arrays.sort(trees, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

        // 定义stack来记录点（边）
        int[] stack = new int[trees.length + 5];
        // 记录栈顶的位置
        int peek = 1;
        // 记录被访问过的节点
        boolean[] visited = new boolean[trees.length + 5];

        for (int i = 1; i < trees.length; i++) {
            // 从第一位开始，因为stack[0]就是对应tree[0]的值，取得一个点c
            int[] pointC = trees[i];
            // 判断当前栈顶是否有2个点，如果栈顶位置小于2，则此时栈里面的点构不成边，跳出
            while(peek >= 2) {
                // 然后然后循环判断这个点c与栈里面倒数2个点的的关系，即点A`stack[peek - 1]`和点B`stack[peek]`
                int[] pointA = trees[stack[peek - 1]];
                int[] pointB = trees[stack[peek]];
                // 与点A和点C（新取到的点），之间的叉积是否大于0，
                if(getArea(pointA, pointB, pointC) > 0) {
                    // 如果大于0，表示边AC比边AB更加靠外，此时将B点推出，表现在栈顶peek位置前移
                    // 然后再进行判断，此时由于点B出栈，则点A即trees[stack[peek - 1]]变成点B，而点A前面一个点peek -- 后的trees[stack[peek - 1]]变成新的点A，再次按照上述逻辑进行判断。
                    int currentStack = stack[peek];
                    visited[currentStack] = false;
                    peek--;
                } else {
                    // 否则，则跳出判断
                    break;
                }
            }
            // 然后，将当前点C存到stack中
            peek++;
            stack[peek] = i;
            visited[i] = true;
        }

        // 这里的size指的是上凸点的长度
        int size = peek;
        // 接着，从右往左，再次判断，这里生成的是下半部分
        for (int i = trees.length - 1; i >= 0; i--) {
            if(visited[i]) {
                continue;
            }
            // 老样子，获得一个熟悉的点C
            int[] pointC = trees[i];
            // 这里不能大于2了，因为stack已经保存了n个上凸壳的位置，所以peek大概率会大于2，如果按照peek >= 2来算，
            // 那么下凸壳有点与原有的2个点更靠外，就会删掉上凸壳的点位
            // 所以对于第一次进入这个方法循环，此时点A就是上凸壳最后一个点，而点B就是下凸壳右边的第一个点
            while(peek > size) {
                // 一样取得2个熟悉的点
                int[] pointA = trees[stack[peek - 1]];
                int[] pointB = trees[stack[peek]];
                // 与点A和点C（新取到的点），之间的叉积是否大于0，
                if(getArea(pointA, pointB, pointC) > 0) {
                    // 如果是，那么peek回退一层，和上面做法一样
                    int currentStack = stack[peek];
                    visited[currentStack] = false;
                    peek--;
                } else {
                    // 否则，则跳出判断
                    break;
                }
            }
            // 然后将点C推入
            peek++;
            stack[peek] = i;
            visited[i] = true;
        }
        // 最后结果是peek减去1，因为最后一位是原点，和0位重叠了
        int[][] resultPoint = new int[peek - 1][2];
        // 写入结果
        for (int i = 1; i < peek; i++) {
            resultPoint[i - 1] = trees[stack[i]];
        }
        // 结束
        return resultPoint;
    }
    private double getArea(int[] a, int[] b, int[] c) {
        // 求出ab两点的向量AB
        int[] ab = {b[0] - a[0], b[1] - a[1]};
        // 求出ac两点的向量AC
        int[] ac = {c[0] - a[0], c[1] - a[1]};
        // 叉积
        return ab[0] * ac[1] - ab[1] * ac[0];
    }
}

效率

执行结果：通过

执行用时：7 ms, 在所有 Java 提交中击败了89.45%的用户
内存消耗：43 MB, 在所有 Java 提交中击败了13.76%的用户
通过测试用例：87 / 87