LCP 37. 最小矩形面积 - Java 实现题目概述给定 N 条直线 y kx bk 0求覆盖所有两两交点的最小轴对齐矩形面积。若交点不足或共线则返回 0。核心思路1. 按斜率分桶相同斜率的直线互相平行无交点。每个斜率只保留截距 最小 和 最大 的两条直线。2. 枚举相邻桶凸包上的关键点只可能来自相邻斜率桶之间的直线交点因此只需枚举相邻桶的直线对。3. 统计极值遍历所有候选交点求最小/最大 x 和 y计算面积。时间复杂度 O(n \log n)空间复杂度 O(n)。---Java 代码javaimport java.util.*;class Solution {public double minRecSize(int[][] lines) {int n lines.length;if (n 2) return 0.0;// 1. 按斜率 k 分桶每个桶保留 b 的最小值和最大值TreeMapInteger, int[] map new TreeMap(); // k - [minB, maxB]for (int[] line : lines) {int k line[0], b line[1];int[] range map.get(k);if (range null) {map.put(k, new int[]{b, b});} else {range[0] Math.min(range[0], b);range[1] Math.max(range[1], b);}}// 如果所有直线斜率相同无交点if (map.size() 2) return 0.0;// 2. 构建有效直线列表每个斜率最多2条minB, maxB// 按斜率升序排列Listint[] kbList new ArrayList(); // [k, b]for (Map.EntryInteger, int[] entry : map.entrySet()) {int k entry.getKey();int[] range entry.getValue();kbList.add(new int[]{k, range[0]}); // 最小截距if (range[0] ! range[1]) {kbList.add(new int[]{k, range[1]}); // 最大截距}}// 3. 枚举相邻斜率桶之间的交点统计极值double minX Double.MAX_VALUE, maxX -Double.MAX_VALUE;double minY Double.MAX_VALUE, maxY -Double.MAX_VALUE;// 按斜率分组后的桶列表每个元素是一个斜率对应的所有直线ListListint[] buckets new ArrayList();for (Map.EntryInteger, int[] entry : map.entrySet()) {int k entry.getKey();int[] range entry.getValue();Listint[] bucket new ArrayList();bucket.add(new int[]{k, range[0]});if (range[0] ! range[1]) {bucket.add(new int[]{k, range[1]});}buckets.add(bucket);}// 枚举相邻桶之间的所有直线对for (int i 0; i buckets.size(); i) {int j (i 1) % buckets.size();Listint[] bucket1 buckets.get(i);Listint[] bucket2 buckets.get(j);for (int[] l1 : bucket1) {for (int[] l2 : bucket2) {double[] point intersect(l1[0], l1[1], l2[0], l2[1]);if (point ! null) {minX Math.min(minX, point[0]);maxX Math.max(maxX, point[0]);minY Math.min(minY, point[1]);maxY Math.max(maxY, point[1]);}}}}// 4. 判断结果if (minX Double.MAX_VALUE) return 0.0;if (Math.abs(maxX - minX) 1e-9 || Math.abs(maxY - minY) 1e-9) {return 0.0;}return (maxX - minX) * (maxY - minY);}// 计算两条直线 y k1*x b1 和 y k2*x b2 的交点// 返回 [x, y]平行则返回 nullprivate double[] intersect(int k1, int b1, int k2, int b2) {if (k1 k2) return null; // 平行double x (double) (b2 - b1) / (k1 - k2);double y k1 * x b1;return new double[]{x, y};}}---复杂度分析指标 复杂度 说明时间 O(n \log n) TreeMap 排序 桶间枚举相邻桶最多 2 \times 2 4 对空间 O(n) 分桶存储每个斜率最多2条直线关键点说明- 分桶去重相同斜率只保留截距极值因为中间直线的交点一定被极值直线的交点覆盖。- 相邻桶枚举凸包的边界点只可能由相邻斜率的直线产生无需枚举所有 O(n^2) 对。- 环形处理使用 (i 1) % size 确保首尾斜率也进行枚举虽然凸包分析中通常只需相邻但实现上保留更稳妥。
`)
