Medium

题目描述

给你一个二维整数数组 squares。每个 squares[i] = [xi, yi, li] 表示一个与 x 轴平行的正方形的左下角坐标和边长。

找到一条水平线的最小 y 坐标值，使得线上方正方形的总面积等于线下方正方形的总面积。

答案误差在 10^-5 范围内将被接受。

注意： 正方形可能重叠。重叠的区域应该被多次计算。

示例 1：

输入：squares = [[0,0,1],[2,2,1]]
输出：1.00000
解释：y = 1 和 y = 2 之间的任何水平线上方都有 1 个单位面积，下方也有 1 个单位面积。最低选项是 1。

示例 2：

输入：squares = [[0,0,2],[1,1,1]]
输出：1.16667
解释：
- 线下方面积：7/6 * 2 (红色) + 1/6 (蓝色) = 15/6 = 2.5
- 线上方面积：5/6 * 2 (红色) + 5/6 (蓝色) = 15/6 = 2.5
由于线上方和下方的面积相等，输出为 7/6 = 1.16667。

提示：

  • 1 <= squares.length <= 5 * 10^4
  • squares[i] = [xi, yi, li]
  • squares[i].length == 3
  • 0 <= xi, yi <= 10^9
  • 1 <= li <= 10^9
  • 所有正方形的总面积不会超过 10^12

解题思路

解题思路

这道题需要找到一条水平线，使得线上方和下方的正方形面积相等。关键在于如何计算给定 y 坐标处的上下面积分布。

核心思路：

  1. 离散化关键点：收集所有正方形的上边界和下边界 y 坐标，这些是面积变化的关键点
  2. 二分搜索：在这些关键点之间进行二分搜索，寻找使上下面积相等的分割线
  3. 面积计算：对于任意 y 坐标，计算每个正方形被分割线切分后的上下部分面积

面积计算方法：

对于正方形 [x, y, l]：

  • 如果分割线 y 坐标为 line_y
  • 下方面积：max(0, min(line_y, y + l) - y) * l
  • 上方面积：max(0, y + l - max(line_y, y)) * l

算法步骤：

  1. 收集所有正方形的 y 坐标边界点
  2. 对边界点排序去重
  3. 使用二分搜索在边界点间寻找平衡点
  4. 计算总面积并验证上下平衡条件

时间复杂度主要来自二分搜索和面积计算，空间复杂度用于存储边界点。

代码实现

class Solution {
public:
    double separateSquares(vector<vector<int>>& squares) {
        vector<long long> points;
        long long totalArea = 0;
        
        for (auto& square : squares) {
            long long x = square[0], y = square[1], l = square[2];
            points.push_back(y);
            points.push_back(y + l);
            totalArea += l * l;
        }
        
        sort(points.begin(), points.end());
        points.erase(unique(points.begin(), points.end()), points.end());
        
        auto calculateBelow = [&](double lineY) -> double {
            double below = 0;
            for (auto& square : squares) {
                long long x = square[0], y = square[1], l = square[2];
                double overlap = max(0.0, min(lineY, (double)(y + l)) - y);
                below += overlap * l;
            }
            return below;
        };
        
        double left = points[0], right = points.back();
        double target = totalArea / 2.0;
        
        for (int iter = 0; iter < 100; iter++) {
            double mid = (left + right) / 2;
            double belowArea = calculateBelow(mid);
            
            if (belowArea < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        
        return (left + right) / 2;
    }
};

class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        points = []
        total_area = 0
        
        for x, y, l in squares:
            points.extend([y, y + l])
            total_area += l * l
        
        points = sorted(set(points))
        
        def calculate_below(line_y):
            below = 0
            for x, y, l in squares:
                overlap = max(0, min(line_y, y + l) - y)
                below += overlap * l
            return below
        
        left, right = points[0], points[-1]
        target = total_area / 2.0
        
        for _ in range(100):
            mid = (left + right) / 2
            below_area = calculate_below(mid)
            
            if below_area < target:
                left = mid
            else:
                right = mid
        
        return (left + right) / 2

public class Solution {
    public double SeparateSquares(int[][] squares) {
        var points = new List<long>();
        long totalArea = 0;
        
        foreach (var square in squares) {
            long x = square[0], y = square[1], l = square[2];
            points.Add(y);
            points.Add(y + l);
            totalArea += l * l;
        }
        
        points = points.Distinct().OrderBy(p => p).ToList();
        
        double CalculateBelow(double lineY) {
            double below = 0;
            foreach (var square in squares) {
                long x = square[0], y = square[1], l = square[2];
                double overlap = Math.Max(0, Math.Min(lineY, y + l) - y);
                below += overlap * l;
            }
            return below;
        }
        
        double left = points[0], right = points[points.Count - 1];
        double target = totalArea / 2.0;
        
        for (int iter = 0; iter < 100; iter++) {
            double mid = (left + right) / 2;
            double belowArea = CalculateBelow(mid);
            
            if (belowArea < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        
        return (left + right) / 2;
    }
}

var separateSquares = function(squares) {
    const points = [];
    let totalArea = 0;
    
    for (const [x, y, l] of squares) {
        points.push(y, y + l);
        totalArea += l * l;
    }
    
    const uniquePoints = [...new Set(points)].sort((a, b) => a - b);
    
    const calculateBelow = (lineY) => {
        let below = 0;
        for (const [x, y, l] of squares) {
            const overlap = Math.max(0, Math.min(lineY, y + l) - y);
            below += overlap * l;
        }
        return below;
    };
    
    let left = uniquePoints[0];
    let right = uniquePoints[uniquePoints.length - 1];
    const target = totalArea / 2.0;
    
    for (let iter = 0; iter < 100; iter++) {
        const mid = (left + right) / 2;
        const belowArea = calculateBelow(mid);
        
        if (belowArea < target) {
            left = mid;
        } else {
            right = mid;
        }
    }
    
    return (left + right) / 2;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n log n + n log(max_coord))排序 O(n log n)，二分搜索进行 log(max_coord) 次迭代，每次计算面积 O(n)
空间复杂度O(n)存储边界点数组