2025-08-20:分割正方形Ⅰ。用go语言，给定一个二维整数数组 squa
2025-08-20：分割正方形Ⅰ。用go语言，给定一个二维整数数组 squares，其中每个元素 squares[i] = [xi, yi, li] 表示一个与 x 轴平行的正方形：左下角坐标为 (xi, yi)，边长为 li。
在平面上任选一条水平直线 y = h。对于每个正方形，位于该直线之上的那部分（若有）算入“上方面积”，位于直线之下的那部分（若有）算入“下方面积”。注意如果多个正方形的区域重合，重叠部分要按各自所属的正方形分别累加（即重复计数）。
目标是求出最小的 h，使得“上方面积”的总和等于“下方面积”的总和。答案与正确值的绝对误差在 1e-5 以内即视为正确。
1 <= squares.length <= 5 * 10000。
squares[i] = [xi, yi, li]。
squares[i].length == 3。
0 <= xi, yi <= 1000000000。
1 <= li <= 1000000000。
所有正方形的总面积不超过 1000000000000。
输入： 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。
题目来自力扣3453。
解决步骤
1. 计算总面积：
o 遍历所有正方形，计算每个正方形的面积（li * li），并累加得到总面积 totArea。
o 因为我们需要“上方面积”和“下方面积”各占一半，所以目标是将平面分为两部分，每部分的面积为 totArea / 2。
2. 事件点（关键点）的提取：
o 每个正方形的上下边界（yi 和 yi + li）是可能改变“上方面积”和“下方面积”的关键点。在这些点之间，面积的变化是线性的。
o 使用一个字典（或哈希表）diff 来记录这些关键点。对于每个正方形：
o 在 y = yi 处，增加 li（表示从 yi 开始，有一个长度为 li 的矩形底边开始影响面积）。
o 在 y = yi + li 处，减少 li（表示从 yi + li 开始，这个矩形底边不再影响面积）。
o 这样，diff 的键是所有正方形的上下边界，值是对应的 li 的增减量。
3. 排序关键点：
o 将 diff 的键（即所有关键点）提取出来并排序，得到一个有序的 y 坐标列表 ys。
4. 扫描计算面积：
o 初始化当前累积的底边长度 sumL 和累积的面积 area。
o 遍历排序后的关键点 ys，对于每一对相邻的关键点 ys[i] 和 ys[i+1]：
o 更新 sumL：sumL += diff[ys[i]]（即当前区间内的矩形底边长度之和）。
o 计算当前区间的高度：h = ys[i+1] - ys[i]。
o 计算当前区间贡献的面积：area += sumL * h。
o 如果 area * 2 >= totArea，说明我们已经跨过了目标点，此时需要精确计算 h 的位置：
o 当前区间的面积贡献是 sumL * h，我们需要找到 h 的具体位置使得累积面积等于 totArea / 2。
o 设需要的额外高度为 delta_h = (totArea / 2 - (area - sumL * h)) / sumL。
o 因此，h = ys[i] + delta_h。
o 返回 h 的值。
示例分析
以输入 squares = [[0,0,2],[1,1,1]] 为例：
1. 总面积：
o 第一个正方形面积：2 * 2 = 4。
o 第二个正方形面积：1 * 1 = 1。
o 总面积 totArea = 5，目标每部分面积为 2.5。
2. 关键点：
o 第一个正方形：y = 0（+2），y = 2（-2）。
o 第二个正方形：y = 1（+1），y = 2（-1）。
o diff = {0: 2, 1: 1, 2: -3}。
o 排序后的 ys = [0, 1, 2]。
3. 扫描：
o i = 0（区间 [0, 1]）：
o sumL = 2。
o h = 1 - 0 = 1。
o area = 2 * 1 = 2。
o 2 < 2.5，继续。
o i = 1（区间 [1, 2]）：
o sumL = 2 + 1 = 3。
o h = 2 - 1 = 1。
o area = 2 + 3 * 1 = 5。
o 5 >= 2.5 * 2 = 5，停止。
o 需要计算精确的 h：
o 前一个 area = 2，还需要 0.5。
o delta_h = 0.5 / 3 = 1/6。
o h = 1 + 1/6 = 7/6 ≈ 1.16667。
复杂度分析
o 时间复杂度：
- 遍历所有正方形计算总面积和构建 diff：O(n)。
- 对关键点排序：O(m log m)，其中 m 是 diff 的键的数量（最多为 2n）。
- 扫描关键点：O(m)。
- 总时间复杂度：O(n + m log m) = O(n log n)（因为 m ≤ 2n）。
o 空间复杂度：
- 存储 diff：O(m) = O(n)。
- 存储排序后的 ys：O(m) = O(n)。
- 总空间复杂度：O(n)。
Go完整代码如下：
package main
import (
"fmt"
"slices"
"maps"
)
func separateSquares(squares [][]int)float64 {
totArea := 0
diff := map[int]int{}
for _, sq := range squares {
y, l := sq[1], sq[2]
totArea += l * l
diff[y] += l
diff[y+l] -= l
}
ys := slices.Sorted(maps.Keys(diff))
area, sumL := 0, 0
for i := 0; ; i++ {
sumL += diff[ys[i]] // 矩形底边长度之和
area += sumL * (ys[i+1] - ys[i]) // 底边长 * 高 = 新增面积
if area*2 >= totArea {
returnfloat64(ys[i+1]) - float64(area*2-totArea)/float64(sumL*2)
}
}
}
func main() {
squares := [][]int{{0,0,2},{1,1,1}}
result := separateSquares(squares)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
from collections import defaultdict
from typing import List
def separate_squares(squares: List[List[int]]) -> float:
if not squares:
return0.0
tot_area = 0
diff = defaultdict(int)
for x, y, l in squares:
tot_area += l * l
diff[y] += l
diff[y + l] -= l
ys = sorted(diff.keys())
area = 0 # 已累计面积（从最小 y 向上）
sum_l = 0 # 当前水平带上所有正方形的水平总长度
for i in range(len(ys) - 1):
sum_l += diff[ys[i]] # 在 y = ys[i] 处更新当前水平长度
delta = ys[i + 1] - ys[i] # 当前水平带的高度
area_prev = area
area += sum_l * delta # 将整段高度加入累计面积
# 检查是否越过总面积的一半
if area * 2 >= tot_area:
half = tot_area / 2.0
remaining = half - area_prev # 还需要的面积（在本段内）
# remaining / sum_l 为在本段内需要向上移动的高度
return ys[i] + remaining / sum_l
# 理论上不应到这里，除非输入有异常（例如 tot_area==0）
return float(ys[-1])
if __name__ == "__main__":
squares = [[0, 0, 2], [1, 1, 1]]
result = separate_squares(squares)
print(result) # 约为 1.1666666666666667·
我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。
欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展
·