LeetCode 题解工作台
分割正方形 I
给你一个二维整数数组 squares ，其中 squares[i] = [x i , y i , l i ] 表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。 找到一个 最小的 y 坐标，它对应一条水平线，该线需要满足它以上正方形的总面积 等于 该线以下正方形的总面积。 答案如果与实际答案…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
根据题意，我们需要找到一个水平线，使得该线以上正方形的总面积等于该线以下正方形的总面积。由于随着 坐标的增加，线以下的面积会增加，线以上的面积会减少，因此我们可以使用二分查找来找到这个水平线的 坐标。 我们定义二分查找的左边界 $l = 0$，右边界 $r = \max(y_i + l_i)$，即所有正方形的最高点。然后我们计算中间点 $mid = (l + r) / 2$，并计算该水平线以下…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个二维整数数组 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 平方单位的面积在其下方。最小的 y 坐标是 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 * 104squares[i] = [xi, yi, li]squares[i].length == 30 <= xi, yi <= 1091 <= li <= 109- 所有正方形的总面积不超过
1012。
解题思路
方法一：二分查找
根据题意，我们需要找到一个水平线，使得该线以上正方形的总面积等于该线以下正方形的总面积。由于随着 坐标的增加，线以下的面积会增加，线以上的面积会减少，因此我们可以使用二分查找来找到这个水平线的 坐标。
我们定义二分查找的左边界 ，右边界 ，即所有正方形的最高点。然后我们计算中间点 ，并计算该水平线以下的面积。如果该面积大于等于总面积的一半，则说明我们需要向下移动右边界 ，否则向上移动左边界 。我们重复这个过程，直到左右边界的差小于一个很小的值（例如 ）。
时间复杂度 ，其中 是正方形的数量，而 , 。空间复杂度 。
class Solution:
def separateSquares(self, squares: List[List[int]]) -> float:
def check(y1: float) -> bool:
t = 0
for _, y, l in squares:
if y < y1:
t += l * min(y1 - y, l)
return t >= s / 2
s = sum(a[2] * a[2] for a in squares)
l, r = 0, max(a[1] + a[2] for a in squares)
eps = 1e-5
while r - l > eps:
mid = (l + r) / 2
if check(mid):
r = mid
else:
l = mid
return r
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Assess understanding of binary search over valid answer space.
- question_mark
Check how the candidate handles floating-point precision in area calculations.
- question_mark
Evaluate the candidate's approach to optimizing performance for large inputs.
常见陷阱
外企场景- error
Failing to correctly handle floating-point precision when comparing areas.
- error
Overcomplicating the area calculations instead of using a simple and efficient method.
- error
Not adjusting the search range in binary search properly, leading to incorrect results.
进阶变体
外企场景- arrow_right_alt
Handling larger numbers of squares efficiently.
- arrow_right_alt
Modifying the problem to account for non-axis-aligned squares.
- arrow_right_alt
Improving performance with specialized techniques for faster area computation.