2025-08-21：分割正方形Ⅱ。用go语言，给你一个二维整数数组 squares，其中每个元素 [xi, yi, li] 表示一个与 x 轴平行的正方形：左下角坐标为 (xi, yi)，边长为 li。请寻找最小的实数 Y，使水平直线 y = Y 将所有正方形的并集划分成上下两部分，且上半部分的面积与下半部分的面积相等。正方形之间可能相互覆盖，重叠区域只计入一次。答案以绝对误差不超过 视为正确。
1 <= squares.length <= 5 * 10000。
squares[i] = [xi, yi, li]。
squares[i].length == 3。
0 <= xi, yi <= 1000000000。
1 <= li <= 1000000000。
所有正方形的总面积不超过 1000000000000000。
输入： squares = [[0,0,1],[2,2,1]]。
输出： 1.00000。
解释：
任何在 y = 1 和 y = 2 之间的水平线都会有 1 平方单位的面积在其上方，1 平方单位的面积在其下方。最小的 y 坐标是 1。
题目来自力扣3454。
分步骤描述过程
1.问题分析：
给定多个与x轴平行的正方形（可能重叠），需要找到一条水平线y=Y，使得所有正方形并集被分成上下两部分，且上下面积相等（总面积的一半）。由于正方形可能重叠，重叠区域只算一次，因此需要计算并集的面积。2.离散化横坐标：
• 提取所有正方形的左右边界（即xi和xi+li），排序并去重，得到离散化的横坐标数组xs。这些横坐标将x轴分成多个区间（线段树中的叶子节点），每个区间长度（xs[i+1]-xs[i]）作为线段树中该节点维护的底边长度。
3.事件处理：
• 为每个正方形生成两个事件：下边界（yi）处增加覆盖（delta=1），上边界（yi+li）处减少覆盖（delta=-1）。将所有事件按y坐标排序。
4.线段树初始化：
• 线段树每个节点维护一段横坐标区间[lx, rx]的信息：
• minCover：该区间内被矩形覆盖的最小次数（实际上这里维护的是当前区间被覆盖的次数，但通过懒标记更新整个子树）。
• minCoverLen：该区间内被覆盖次数等于minCover的底边长之和（用于计算未被覆盖的长度）。
• todo：懒标记，表示子树需要增加的覆盖次数（用于延迟更新）。
• 建树：初始化线段树，叶子节点的minCover为0（初始未被覆盖），minCoverLen为对应区间的长度（xs[i+1]-xs[i]）。
5.扫描线过程：
• 按y坐标从小到大处理事件（模拟从下往上扫描）：
• 对于每个事件（y, lx, rx, delta），找到其对应的离散化区间[l, r]（l为lx在xs中的索引，r为rx在xs中的索引减1）。
• 更新线段树：将区间[l, r]的覆盖次数增加delta（通过线段树的区间更新，包括懒标记处理）。
• 更新后，根节点维护整个x轴区间的信息：minCover表示整个区间被覆盖的最小次数（实际上根节点的minCover就是整个区间的最小覆盖次数，但这里我们关心是否被覆盖过？实际上，根节点的minCover为0表示有部分区间未被覆盖，否则全部被覆盖至少一次）。
• 计算当前被至少一个矩形覆盖的底边总长度sumLen：总长度（xs[-1]-xs[0]）减去未被覆盖的长度（即根节点minCover为0时，minCoverLen就是未被覆盖的长度，否则为0）。
• 记录当前事件处理后的累计面积（totArea）和当前的sumLen（用于后续二分）。累计面积的计算：从上一次事件到当前事件的高度差（events[i+1].y - e.y）乘以当前的sumLen，得到这一段的面积，并累加到totArea。
6.二分查找分割线：
• 总面积为totArea（所有正方形并集的面积），目标是找到y=Y使得下半部分面积为totArea/2。
• 在records中记录每个事件处理后的累计面积（当前事件之前的累计面积）和当前的sumLen（底边被覆盖的长度）。
• 二分查找最后一个累计面积小于totArea/2的事件索引i（即records[i].area < totArea/2 <= records[i+1].area）。
• 分割线Y的位置：从事件i对应的y坐标（events[i].y）开始，还需要上升的高度为（剩余面积差）除以（当前的底边被覆盖长度sumLen）。即：
Y = events[i].y + (totArea/2 - records[i].area) / records[i].sumLen
7.输出结果：
计算得到的Y即为答案，要求绝对误差不超过1e-5。
时间复杂度和额外空间复杂度
•时间复杂度：
• 离散化（排序去重）：O(n log n)，n为正方形数量（最多2n个坐标）。
• 事件排序：O(n log n)。
• 线段树建树：O(n)（实际节点数最多4N，N为离散化后区间数）。
• 线段树每次更新和查询：O(log n)（每次事件处理更新区间，最多2n次事件）。
• 二分查找：O(log n)。
• 总时间复杂度：O(n log n)。
•额外空间复杂度：
• 离散化数组xs：O(n)。
• 事件数组events：O(n)。
• 线段树：O(n)（节点数最多4N，N为离散化后区间数，最多2n个点，区间数最多2n-1）。
• records数组：O(n)。
• 总空间复杂度：O(n)。
注意：n为正方形数量（输入规模），但离散化后区间数最多为2n（去重后可能更少），因此线段树节点数为O(n)。所有操作都是基于n的多项式级别。
Go完整代码如下：
package main import ( "fmt" "math/bits" "slices" "sort" ) // 线段树每个节点维护一段横坐标区间 [lx, rx] type seg []struct { l, r int minCoverLen int// 区间内被矩形覆盖次数最少的底边长之和 minCover int// 区间内被矩形覆盖的最小次数 todo int// 子树内的所有节点的 minCover 需要增加的量，注意这可以是负数 } // 根据左右儿子的信息，更新当前节点的信息 func (t seg) maintain(o int) { lo, ro := &t[o<<1], &t[o<<1|1] mn := min(lo.minCover, ro.minCover) t[o].minCover = mn t[o].minCoverLen = 0 if lo.minCover == mn { // 只统计等于 minCover 的底边长之和 t[o].minCoverLen = lo.minCoverLen } if ro.minCover == mn { t[o].minCoverLen += ro.minCoverLen } } // 仅更新节点信息，不下传懒标记 todo func (t seg) do(o, v int) { t[o].minCover += v t[o].todo += v } // 下传懒标记 todo func (t seg) spread(o int) { v := t[o].todo if v != 0 { t.do(o<<1, v) t.do(o<<1|1, v) t[o].todo = 0 } } // 建树 func (t seg) build(xs []int, o, l, r int) { t[o].l, t[o].r = l, r t[o].todo = 0 if l == r { t[o].minCover = 0 t[o].minCoverLen = xs[l+1] - xs[l] return } m := (l + r) >> 1 t.build(xs, o<<1, l, m) t.build(xs, o<<1|1, m+1, r) t.maintain(o) } // 区间更新 func (t seg) update(o, l, r, v int) { if l <= t[o].l && t[o].r <= r { t.do(o, v) return } t.spread(o) m := (t[o].l + t[o].r) >> 1 if l <= m { t.update(o<<1, l, r, v) } if m < r { t.update(o<<1|1, l, r, v) } t.maintain(o) } // 代码逻辑同 850 题，增加一个 records 数组记录关键数据 func separateSquares(squares [][]int)float64 { m := len(squares) * 2 xs := make([]int, 0, m) type event struct{ y, lx, rx, delta int } events := make([]event, 0, m) for _, sq := range squares { lx, y, l := sq[0], sq[1], sq[2] rx := lx + l xs = append(xs, lx, rx) events = append(events, event{y, lx, rx, 1}, event{y + l, lx, rx, -1}) } // 排序去重，方便离散化 slices.Sort(xs) xs = slices.Compact(xs) // 初始化线段树 n := len(xs) - 1// len(xs) 个横坐标有 len(xs)-1 个差值 t := make(seg, 2< uint (n -1 ))) t.build(xs, 1 , 0 , n -1 ) // 模拟扫描线从下往上移动 slices.SortFunc(events, func(a, b event) int { return a.y - b.y }) type pair struct { area, sumLen int } records := make ([]pair, m -1 ) totArea := 0 for i, e := range events[:m -1 ] { l := sort.SearchInts(xs, e.lx) r := sort.SearchInts(xs, e.rx) - 1 // 注意 r 对应着 xs[r] 与 xs[r+1]=e.rx 的差值 t.update( 1 , l, r, e.delta) // 更新被 [e.lx, e.rx] 覆盖的次数 sumLen := xs[ len (xs) -1 ] - xs[ 0 ] // 总的底边长度 if t[ 1 ].minCover == 0 { // 需要去掉没被矩形覆盖的长度 sumLen -= t[ 1 ].minCoverLen } records[i] = pair{totArea, sumLen} // 记录关键数据 totArea += sumLen * (events[i+ 1 ].y - e.y) // 新增面积 = 被至少一个矩形覆盖的底边长之和 * 矩形高度 } // 二分找最后一个 < totArea / 2 的面积 i := sort.Search(m -1 , func(i int) bool { return records[i].area* 2 >= totArea }) - 1 return float64 (events[i].y) + float64 (totArea-records[i].area* 2 )/ float64 (records[i].sumLen* 2 ) } func main() { squares := [][] int {{ 0 , 0 , 1 },{ 2 , 2 , 1 }} result := separateSquares(squares) fmt.Println(result) }
Python完整代码如下：
# -*-coding:utf-8-*- import bisect class SegTree: def __init__(self, xs): self.n = len(xs) - 1 self.xs = xs self.size = 1 while self.size < self.n: self.size *= 2 self.min_cover = [0] * (2 * self.size) self.min_cover_len = [0] * (2 * self.size) self.todo = [0] * (2 * self.size) # 初始化叶子节点 for i in range(self.n): self.min_cover_len[self.size + i] = xs[i+1] - xs[i] for i in range(self.n, self.size): self.min_cover_len[self.size + i] = 0 for i in range(self.size - 1, 0, -1): self.maintain(i) def maintain(self, o): lo, ro = 2*o, 2*o+1 mn = min(self.min_cover[lo], self.min_cover[ro]) self.min_cover[o] = mn self.min_cover_len[o] = 0 if self.min_cover[lo] == mn: self.min_cover_len[o] += self.min_cover_len[lo] if self.min_cover[ro] == mn: self.min_cover_len[o] += self.min_cover_len[ro] def do(self, o, v): self.min_cover[o] += v self.todo[o] += v def spread(self, o): if self.todo[o] != 0: self.do(2*o, self.todo[o]) self.do(2*o+1, self.todo[o]) self.todo[o] = 0 def update(self, l, r, v, o=1, segL=0, segR=None): if segR is None: segR = self.size - 1 if l <= segL and segR <= r: self.do(o, v) return self.spread(o) mid = (segL + segR) // 2 if l <= mid: self.update(l, r, v, 2*o, segL, mid) if mid < r: self.update(l, r, v, 2*o+1, mid+1, segR) self.maintain(o) def separateSquares(squares): m = len(squares) * 2 xs = [] events = [] for sq in squares: lx, y, l = sq rx = lx + l xs.extend([lx, rx]) events.append((y, lx, rx, 1)) events.append((y + l, lx, rx, -1)) xs = sorted(set(xs)) events.sort(key=lambda x: x[0]) n = len(xs) - 1 seg_tree = SegTree(xs) records = [] tot_area = 0 for i in range(len(events) - 1): y, lx, rx, delta = events[i] l = bisect.bisect_left(xs, lx) r = bisect.bisect_left(xs, rx) - 1 seg_tree.update(l, r, delta) total_len = xs[-1] - xs[0] if seg_tree.min_cover[1] == 0: total_len -= seg_tree.min_cover_len[1] records.append((tot_area, total_len)) next_y = events[i+1][0] tot_area += total_len * (next_y - y) # 二分查找 target = tot_area / 2 left, right = 0, len(records) while left < right: mid = (left + right) // 2 if records[mid][0] * 2 >= tot_area: right = mid else: left = mid + 1 i = left - 1 if i < 0: return float(events[0][0]) prev_area, total_len = records[i] prev_y = events[i][0] remaining_area = tot_area / 2 - prev_area return prev_y + remaining_area / total_len def main(): squares = [[0, 0, 1], [2, 2, 1]] result = separateSquares(squares) print(result) if __name__ == "__main__": main()
我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。 欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展
热门跟贴