2025-08-20：分割正方形Ⅰ。用go语言，给定一个二维整数数组 squares，其中每个元素 squares[i] = [

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. 1. 计算总面积：
   • • 遍历所有正方形，计算每个正方形的面积（li * li），并累加得到总面积 totArea。
   • • 因为我们需要“上方面积”和“下方面积”各占一半，所以目标是将平面分为两部分，每部分的面积为 totArea / 2。
2. 2. 事件点（关键点）的提取：
   • • 每个正方形的上下边界（yi 和 yi + li）是可能改变“上方面积”和“下方面积”的关键点。在这些点之间，面积的变化是线性的。
   • • 使用一个字典（或哈希表）diff 来记录这些关键点。对于每个正方形：
     • • 在 y = yi 处，增加 li（表示从 yi 开始，有一个长度为 li 的矩形底边开始影响面积）。
     • • 在 y = yi + li 处，减少 li（表示从 yi + li 开始，这个矩形底边不再影响面积）。
   • • 这样，diff 的键是所有正方形的上下边界，值是对应的 li 的增减量。
3. 3. 排序关键点：
   • • 将 diff 的键（即所有关键点）提取出来并排序，得到一个有序的 y 坐标列表 ys。
4. 4. 扫描计算面积：
   • • 初始化当前累积的底边长度 sumL 和累积的面积 area。
   • • 遍历排序后的关键点 ys，对于每一对相邻的关键点 ys[i] 和 ys[i+1]：
     • • 更新 sumL：sumL += diff[ys[i]]（即当前区间内的矩形底边长度之和）。
     • • 计算当前区间的高度：h = ys[i+1] - ys[i]。
     • • 计算当前区间贡献的面积：area += sumL * h。
     • • 如果 area * 2 >= totArea，说明我们已经跨过了目标点，此时需要精确计算 h 的位置：
       • • 当前区间的面积贡献是 sumL * h，我们需要找到 h 的具体位置使得累积面积等于 totArea / 2。
       • • 设需要的额外高度为 delta_h = (totArea / 2 - (area - sumL * h)) / sumL。
       • • 因此，h = ys[i] + delta_h。
       • • 返回 h 的值。

示例分析

以输入 squares = [[0,0,2],[1,1,1]] 为例：

1. 1. 总面积：
   • • 第一个正方形面积：2 * 2 = 4。
   • • 第二个正方形面积：1 * 1 = 1。
   • • 总面积 totArea = 5，目标每部分面积为 2.5。
2. 2. 关键点：
   • • 第一个正方形：y = 0（+2），y = 2（-2）。
   • • 第二个正方形：y = 1（+1），y = 2（-1）。
   • • diff = {0: 2, 1: 1, 2: -3}。
   • • 排序后的 ys = [0, 1, 2]。
3. 3. 扫描：
   • • i = 0（区间 [0, 1]）：
     • • sumL = 2。
     • • h = 1 - 0 = 1。
     • • area = 2 * 1 = 2。
     • • 2 < 2.5，继续。
   • • i = 1（区间 [1, 2]）：
     • • sumL = 2 + 1 = 3。
     • • h = 2 - 1 = 1。
     • • area = 2 + 3 * 1 = 5。
     • • 5 >= 2.5 * 2 = 5，停止。
   • • 需要计算精确的 h：
     • • 前一个 area = 2，还需要 0.5。
     • • delta_h = 0.5 / 3 = 1/6。
     • • h = 1 + 1/6 = 7/6 ≈ 1.16667。

复杂度分析

• • 时间复杂度：
  • • 遍历所有正方形计算总面积和构建 diff：O(n)。
  • • 对关键点排序：O(m log m)，其中 m 是 diff 的键的数量（最多为 2n）。
  • • 扫描关键点：O(m)。
  • • 总时间复杂度：O(n + m log m) = O(n log n)（因为 m ≤ 2n）。
• • 空间复杂度：
  • • 存储 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 语言和算法助力您的职业发展