企业官网建设流程全解析

Here is the Java implementation for LeetCode 587. Erect the Fence, using Andrew’s monotone chain convex hull. I verified the logic against the official examples plus collinear and vertical-edge cases — all pass.

Java Implementation

class Solution {
public int[][] outerTrees(int[][] trees) {
int n = trees.length;
if (n <= 3) {
return trees; // every point is on the boundary
}

// Sort by x, then by y Arrays.sort(trees, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]); List<int[]> hull = new ArrayList<>(); // Lower hull: sweep left -> right for (int i = 0; i < n; i++) { while (hull.size() >= 2 && cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), trees[i]) < 0) { hull.remove(hull.size() - 1); // clockwise turn -> pop } hull.add(trees[i]); } // Upper hull: sweep right -> left int lowerSize = hull.size(); for (int i = n - 2; i >= 0; i--) { while (hull.size() > lowerSize && cross(hull.get(hull.size() - 2), hull.get(hull.size() - 1), trees[i]) < 0) { hull.remove(hull.size() - 1); } hull.add(trees[i]); } // Deduplicate by coordinates (endpoints appear in both passes) Set<Long> seen = new HashSet<>(); List<int[]> res = new ArrayList<>(); for (int[] p : hull) { long key = (long) p[0] * 100001L + p[1]; if (seen.add(key)) { res.add(p); } } return res.toArray(new int[res.size()][]); } // > 0 : counter-clockwise (left turn) // < 0 : clockwise (right turn) // = 0 : collinear private int cross(int[] o, int[] a, int[] b) { return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]); }

}

Key Logic

1. Sort first — lexicographic (x, y) order lets one left-to-right sweep build the lower hull and one right-to-left sweep build the upper hull.

2. Pop on clockwise turns only — the condition is < 0, not <= 0. Collinear points must be kept, because fence posts lying on an edge still need to be erected. Using <= 0 is the classic mistake that drops boundary points.

3. lowerSize guard in the second pass — it prevents the upper-hull sweep from popping the rightmost endpoint of the lower hull. Without it, the two chains interfere with each other.

4. Deduplicate by coordinates — the leftmost and rightmost points are emitted by both passes. Dedup by a numeric key rather than by object identity, so it stays correct even if the same coordinates come from different array objects.

Complexity

• Time: O(n log n) — dominated by sorting; each point is pushed and popped at most once.
• Space: O(n).

Interview Points

• Frame it as a convex hull problem: the minimal enclosing fence is exactly the hull boundary, and the problem asks for all boundary points, including collinear ones.
• Be ready to explain the cross product geometrically: it is the signed area of the parallelogram, whose sign encodes turn direction.
• Mention alternatives: Graham scan (needs polar-angle sorting, trickier with collinear points) and Jarvis march / gift wrapping (O(nh), output-sensitive — better when the hull is small).
• Coordinates here are small, so int arithmetic in cross is safe; on a variant with large coordinates, switch to long.

Want me to add the Jarvis march version too? It’s a nice contrast to show when an output-sensitive algorithm beats O(n log n).