1. Leetcode Algorithm Notes - Convex Hull Problem, Andrew's Approach

发表于 更新于 分类于 本文字数： 2.6k 阅读时长 ≈ 10 分钟

【Algorithm Notes】This section is for personal note-taking purposes only, and is not intended for teaching, solving, or explaining problems. Therefore, it is not indexed or commented. Please use official solutions or high-quality solutions provided by authors like Gongshui SanYe for problem-solving. This reminder only appears once.

Yesterday’s Leetcode problem was 587. Erect the Fence. I learned about the convex hull problem and took some notes based on my understanding and the solution provided by Three Leaves (referred to as “Solution” below).(English version Translated by GPT-3.5, 返回中文)

Original Problem

Original problem: Leetcode Daily Problem: 537. Erect the Fence

1
2
3
4
5
6
7
8
9
在一个二维的花园中，有一些用 (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]]

Understanding Andrew’s Algorithm

If you are familiar with the convex hull algorithm, this problem becomes much easier. So, I forced myself to understand it.

  1. The solution uses Andrew’s algorithm to solve this problem. Andrew’s algorithm can be divided into two parts: first, finding the lower convex hull from left to right, and then finding the upper convex hull from right to left. Finally, merging the two results gives us the final answer.

  2. First, find the upper convex hull (indicated in red).

    Upper Convex Hull

  3. Then, find the lower convex hull (indicated in blue).

    Lower Convex Hull

In-depth Understanding

Now that we understand the basic idea, let’s see how it can be implemented.

  1. First, find the leftmost point, which is the point closest to the origin. To do this, first sort the coordinates (x, y) by x-coordinate and then by y-coordinate. This way, the point at index 0 will be the closest to the origin.
  2. Use a stack array variable to maintain each edge (which consists of at least two points). Also, maintain an integer variable to record the index of the top of the stack. Define a visited array to record the visited nodes. The stack will store points (x, y), and each pair of adjacent points will form an edge.
  3. Starting from index 1 (because index 0 is the starting point x, y), take a point C and continuously check if the number of elements in the stack is at least 2 (because it takes at least 2 points to form an edge). If it’s not, simply push point C onto the stack. If the number of elements in the stack is greater than or equal to 2, take out the last 2 elements from the stack (denoted as points A and B), and form two edges AB and AC with the new point C. Then, calculate the cross product of these two vectors (the calculation method for two points A and B is (Bx - Ax, By - Ay)). If the cross product is greater than 0, it means that AB needs to be rotated clockwise to overlap with AC. This indicates that point C is closer to the outside compared to point B. In this case, pop point B from the stack (and decrement the top index by 1) and push point C onto the stack. Now, the last 2 elements in the stack are points A and C (where C was the previous B).
  4. Continue this process according to the above rules until reaching the rightmost point. At this point, the stack will contain the points of the lower convex hull.
  5. Then, repeat the above process from right to left to find the points of the upper convex hull. Note that while doing this, keep checking if the number of elements in the stack is greater than the total size of the lower convex hull (as the data of the lower convex hull cannot be removed). This will give us the points of the upper convex hull.
  6. Finally, the answer is the value at top of stack - 1, because the value at the top of the stack corresponds to the value of the origin (point 0).
  7. Output the answer and finish.

Implementation of the Logic

Let’s implement the logic step by step. The input data is:

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

  1. First, find the leftmost point. Sort the coordinates as mentioned above, in ascending order of x-coordinate and then y-coordinate.

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

  2. Then, use a stack array variable to maintain each edge, an integer variable to record the index of the top of the stack, and a visited array to record visited points.

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

  3. Starting from index 1, take a point C.

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

  4. Then, check if the current top of the stack has 2 points. Continuously check the relationship between point C and the last two points in the stack, denoted as A (stack[peek-1]) and B (stack[peek]). Calculate the cross product between the two vectors AB and AC (using B’s coordinates subtracted by A’s coordinates: (Bx - Ax, By - Ay)). If the cross product is greater than 0, it means that edge AC is farther outside compared to edge AB. In this case, pop point B from the stack and update the points A and C accordingly. Repeat this process according to the logic mentioned above.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    // 判断当前栈顶是否有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. At this point, the values in stack[0 - peek] represent the points of the lower convex hull. Next, repeat the same process from right to left to find the points of the upper convex hull. Keep checking if the number of elements in the stack is greater than the size of the lower convex hull, as mentioned before.

    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
    // 这里的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. Finally, output the result.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    // 最后结果是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;

Simulation

Complete Code

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
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];
    }
}

Efficiency

1
2
3
4
5
执行结果：通过

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