以下是 LeetCode 3464 的 Java 实现核心思路是二分答案 单调队列优化 DP。解题思路1. 二分答案答案范围是 [0, \text{side}]对最小曼哈顿距离进行二分搜索2. 展开正方形将正方形边界按顺时针展开为一维序列按边分类排序3. 可行性检验对于候选距离 d用单调队列优化的 DP 判断能否选出 k 个点使得相邻点间曼哈顿距离 \ge d完整代码javaimport java.util.*;class Solution {public int maxDistance(int side, int[][] points, int k) {Listint[] ordered getOrderedPoints(side, points);int l 0, r side;while (l r) {int m (l r 1) / 2;if (isValidDistance(ordered, k, m)) {l m;} else {r m - 1;}}return l;}// 判断能否选出 k 个点使得相邻点间曼哈顿距离 dprivate boolean isValidDistance(Listint[] ordered, int k, int d) {DequeSequence dq new ArrayDeque();dq.add(new Sequence(ordered.get(0)[0], ordered.get(0)[1],ordered.get(0)[0], ordered.get(0)[1], 1));int maxLength 1;for (int i 1; i ordered.size(); i) {int x ordered.get(i)[0];int y ordered.get(i)[1];int startX x, startY y;int length 1;// 维护单调队列保留能作为起点的序列while (!dq.isEmpty() manhattan(x, y, dq.peekFirst().endX, dq.peekFirst().endY) d) {Sequence first dq.peekFirst();if (manhattan(x, y, first.startX, first.startY) d first.length 1 length) {startX first.startX;startY first.startY;length first.length 1;maxLength Math.max(maxLength, length);}dq.pollFirst();}dq.addLast(new Sequence(startX, startY, x, y, length));}return maxLength k;}// 曼哈顿距离private int manhattan(int x1, int y1, int x2, int y2) {return Math.abs(x1 - x2) Math.abs(y1 - y2);}// 将正方形边界上的点按顺时针顺序展开private Listint[] getOrderedPoints(int side, int[][] points) {Listint[] left new ArrayList();Listint[] top new ArrayList();Listint[] right new ArrayList();Listint[] bottom new ArrayList();for (int[] point : points) {int x point[0], y point[1];if (x 0 y 0) {left.add(point);} else if (x 0 y side) {top.add(point);} else if (x side y side) {right.add(point);} else {bottom.add(point);}}// 按顺时针方向排序各边上的点left.sort(Comparator.comparingInt(p - p[1])); // 左y 从小到大top.sort(Comparator.comparingInt(p - p[0])); // 上x 从小到大right.sort((a, b) - Integer.compare(b[1], a[1])); // 右y 从大到小bottom.sort((a, b) - Integer.compare(b[0], a[0])); // 下x 从大到小Listint[] ordered new ArrayList();ordered.addAll(left);ordered.addAll(top);ordered.addAll(right);ordered.addAll(bottom);return ordered;}// 记录序列信息private static class Sequence {int startX, startY; // 序列起点int endX, endY; // 序列终点int length; // 序列长度包含的点数Sequence(int startX, int startY, int endX, int endY, int length) {this.startX startX;this.startY startY;this.endX endX;this.endY endY;this.length length;}}}关键点说明要点 说明二分答案 经典最大化最小值问题答案范围 [0, \text{side}]k \ge 4 时答案不超过 \text{side}展开正方形 按顺时针将边界点排成一维序列左(y↑)、上(x↑)、右(y↓)、下(x↓)单调队列优化 DP 状态 dp[i] 表示以第 i 个点结尾的最长合法序列长度。利用单调性队首维护最优起点可行性检验 对于候选距离 d检查是否存在长度 \ge k 的合法序列复杂度分析- 时间复杂度O(n \log \text{side})其中 n \text{points.length}。二分搜索 O(\log \text{side})每次检验 O(n)- 空间复杂度O(n)
Kimi LeetCode 3464. 正方形上的点之间的最大距离 Java实现
以下是 LeetCode 3464 的 Java 实现核心思路是二分答案 单调队列优化 DP。解题思路1. 二分答案答案范围是 [0, \text{side}]对最小曼哈顿距离进行二分搜索2. 展开正方形将正方形边界按顺时针展开为一维序列按边分类排序3. 可行性检验对于候选距离 d用单调队列优化的 DP 判断能否选出 k 个点使得相邻点间曼哈顿距离 \ge d完整代码javaimport java.util.*;class Solution {public int maxDistance(int side, int[][] points, int k) {Listint[] ordered getOrderedPoints(side, points);int l 0, r side;while (l r) {int m (l r 1) / 2;if (isValidDistance(ordered, k, m)) {l m;} else {r m - 1;}}return l;}// 判断能否选出 k 个点使得相邻点间曼哈顿距离 dprivate boolean isValidDistance(Listint[] ordered, int k, int d) {DequeSequence dq new ArrayDeque();dq.add(new Sequence(ordered.get(0)[0], ordered.get(0)[1],ordered.get(0)[0], ordered.get(0)[1], 1));int maxLength 1;for (int i 1; i ordered.size(); i) {int x ordered.get(i)[0];int y ordered.get(i)[1];int startX x, startY y;int length 1;// 维护单调队列保留能作为起点的序列while (!dq.isEmpty() manhattan(x, y, dq.peekFirst().endX, dq.peekFirst().endY) d) {Sequence first dq.peekFirst();if (manhattan(x, y, first.startX, first.startY) d first.length 1 length) {startX first.startX;startY first.startY;length first.length 1;maxLength Math.max(maxLength, length);}dq.pollFirst();}dq.addLast(new Sequence(startX, startY, x, y, length));}return maxLength k;}// 曼哈顿距离private int manhattan(int x1, int y1, int x2, int y2) {return Math.abs(x1 - x2) Math.abs(y1 - y2);}// 将正方形边界上的点按顺时针顺序展开private Listint[] getOrderedPoints(int side, int[][] points) {Listint[] left new ArrayList();Listint[] top new ArrayList();Listint[] right new ArrayList();Listint[] bottom new ArrayList();for (int[] point : points) {int x point[0], y point[1];if (x 0 y 0) {left.add(point);} else if (x 0 y side) {top.add(point);} else if (x side y side) {right.add(point);} else {bottom.add(point);}}// 按顺时针方向排序各边上的点left.sort(Comparator.comparingInt(p - p[1])); // 左y 从小到大top.sort(Comparator.comparingInt(p - p[0])); // 上x 从小到大right.sort((a, b) - Integer.compare(b[1], a[1])); // 右y 从大到小bottom.sort((a, b) - Integer.compare(b[0], a[0])); // 下x 从大到小Listint[] ordered new ArrayList();ordered.addAll(left);ordered.addAll(top);ordered.addAll(right);ordered.addAll(bottom);return ordered;}// 记录序列信息private static class Sequence {int startX, startY; // 序列起点int endX, endY; // 序列终点int length; // 序列长度包含的点数Sequence(int startX, int startY, int endX, int endY, int length) {this.startX startX;this.startY startY;this.endX endX;this.endY endY;this.length length;}}}关键点说明要点 说明二分答案 经典最大化最小值问题答案范围 [0, \text{side}]k \ge 4 时答案不超过 \text{side}展开正方形 按顺时针将边界点排成一维序列左(y↑)、上(x↑)、右(y↓)、下(x↓)单调队列优化 DP 状态 dp[i] 表示以第 i 个点结尾的最长合法序列长度。利用单调性队首维护最优起点可行性检验 对于候选距离 d检查是否存在长度 \ge k 的合法序列复杂度分析- 时间复杂度O(n \log \text{side})其中 n \text{points.length}。二分搜索 O(\log \text{side})每次检验 O(n)- 空间复杂度O(n)
