昨儿周赛430打完不少朋友都在聊第一题“3453. 分割正方形 I”。这题看起来很几何名字也很唬人但拆开来看就是“模拟摆放矩形 二分答案”的组合代码量不大真正容易翻车的点全在判断函数里。这一篇我打算把这道题彻底讲透从题意拆解、check 函数怎么写、为什么能二分、左右边界怎么取再到我实际踩过的几个坑一条线捋下来。无论你是刚开始刷 LeetCode 的选手还是已经在冲每日一题打卡的老手这题都值得花十分钟好好过一遍因为它几乎是周赛第一题的典型模板先写一个单调的判断函数再套二分找极值。1. 先别急着写代码把放置规则拆成三条1.1 题目到底让你做什么题面给了一串矩形的尺寸每个矩形用[width, height]表示并且保证width height也就是说题目已经帮你固定了长宽方向不需要考虑旋转。然后它给了一个正方形要求你把这些矩形按顺序放进去。关键就在“按顺序”和“怎么放”。规则可以概括成三条从正方形底边开始先放第一行从左到右依次放矩形。同一行的所有矩形必须等高度这个高度由该行第一个矩形的高度决定。如果下一个矩形的高度和当前行高度不一样或者当前行的剩余宽度放不下它那就必须结束当前行在它上方新开一行继续放。问的通常有两种给定一个边长判断能不能放下或者更进一步求能放下所有矩形的最小正方形边长。无论题目问的是哪一种核心都是同一个判断函数给定边长side能不能按规则放完所有矩形。所以这篇文章我直接讲更强的一版求最小边长。如果你遇到只问判断的版本直接调用can_place(side, sizes)就行。1.2 一个能记住规则的类比这套放置规则听起来抽象但用生活里的场景一类比就顺了。你可以想象自己在整理一个货架或者乐高底板每一层的“净空高度”由这一层第一件物品的高度决定这一层后面放的每一样东西都必须和它一样高不能高出来一块也不能矮一头。如果下一件物品高度不同或者这层剩余的位置已经塞不下它那就老老实实往上开一层。这个类比能帮你记住两个最容易忽略的细节。第一换行不一定是因为宽度不够高度不同也必须换。很多题解会把“放不下”和“高度不同”合并成一个换行条件其实这正是这道题的灵魂。第二整个摆放过程是有先后顺序的不是把矩形都摊开然后像俄罗斯方块一样自由选择位置而是必须按数组给的顺序一个一个处理。我见过不少人写着写着就想排序一排序整个题意就偏了。1.3 两个容易在读题时漏掉的信息第一个信息是矩形顺序不可变。sizes就是一个等待依次处理的队列队列头部先放放到最后自然结束。不能因为某个矩形“更适合放这里”就把它提前也不能把输入顺序重新排列。这一点在样例里可能不明显因为你随便排也能把例子跑通但一旦面对稍微密集一点的输入顺序不同可能导致完全不同的结果。第二个信息是width height这个约束。它不只是为了编译方便它的真实意义是矩形在放置时不需要考虑“要不要转一下”。如果没有这个约束你还要考虑每个矩形横放还是竖放那个问题的复杂度会瞬间涨上去就不再是简单模拟能搞定的了。题目把这个约束写死等于主动帮你把思考维度砍掉一半。读题时看到这种条件应该条件反射地意识到哦方向固定那么状态就少了。2. 核心一个正确性优先的 check 函数2.1 三个状态变量就够判断函数是整道题的发动机你不需要维护整个正方形的二维矩阵只需要三个变量used_h已经结算过的所有行的总高度也就是当前新行的底边高度。cur_w当前行已经占用的宽度。cur_h当前行的高度它由这一行第一个矩形决定。为什么不需要记录当前行底边的具体位置因为所有行都是从正方形底边开始向上堆叠的每一行结算时把自身高度加到used_h上下一行的底边自然就是新的used_h。这和你叠箱子一样不需要知道箱子在哪一层只需要知道已经叠了多高。2.2 循环体的分支逻辑什么时候换行遍历每个矩形时先做一个防御性判断如果这个矩形的宽度大于side或者高度大于side直接返回False。单个矩形本身就比正方形还大再怎么排都放不进去这个特判越早越好。接着进入主逻辑。如果cur_w 0说明开始了一个新行那么当前行高度cur_h直接取当前矩形的高度。这里要注意新行开在什么位置就在used_h之上但此刻不需要立即累加因为这一行还没结束你不知道它会占多高等结束或最后统一结算。如果cur_w不为零就要判断当前矩形能不能放进当前行。判断条件很直接当前矩形高度不等于 cur_h或者cur_w width side两个条件满足任意一个就说明当前行到此为止。此时先结算旧行used_h cur_h然后开新行cur_w 0cur_h 当前矩形高度。最后无论走哪个分支都要把当前矩形的宽度累加到cur_w上。循环结束后还有一个必须做的动作把最后一行的高度也结算掉。很多人写着写着就漏了这一步因为最后一个矩形放完后循环自然结束不会再有“换行”这个动作帮你去结算最后一行。所以需要判断一下如果最后还有未结算的行就used_h cur_h最终返回used_h side。2.3 手动推一遍验证逻辑闭环光看代码可能觉得绕我手动推一个完整的例子你就能感受到这个流程是怎么闭环的。假设矩形序列是[[4,1],[4,2],[4,2],[4,2]]也就是四个宽度为 4 的矩形高度分别是 1、2、2、2。先看side 6时第一个矩形[4,1]cur_w为 0所以cur_h 1然后cur_w 4。第二个矩形[4,2]cur_w不为 0当前行高度是 1新矩形高度是 2高度不等触发换行。结算used_h 1开新行cur_h 2cur_w 4。第三个矩形[4,2]高度相等但cur_w 4 8 6宽度放不下又触发换行。结算used_h 3开新行cur_h 2cur_w 4。第四个矩形[4,2]同样高度相等但宽度放不下再次换行。结算used_h 5开新行cur_h 2cur_w 4。循环结束最后一行还没结算补上used_h 2 77 大于 6所以side 6放不下。再试side 8前两步和上面一样第二个矩形换行后第三个矩形[4,2]发现高度相等且cur_w 4 8刚好等于side于是不换行直接放进去cur_w变成 8。第四个矩形[4,2]到来时高度相等但cur_w 4 12 8换行。结算used_h 3开新行放第四个cur_w 4。循环结束后补最后一行used_h 5小于等于 8放得下。这个例子很有价值它同时覆盖了“高度不同导致换行”和“宽度不够导致换行”两条路径也暴露了“最后一行必须手工结算”这个最常见的坑。如果你自己推导一遍能跟上那 check 函数这块就过关了。3. 二分答案把“能不能”变成“最小多少”3.1 为什么可以二分可行性随边长单调现在我们已经有了一个判断函数接下来要回答“最小边长是多少”。最朴素的做法是从 1 开始慢慢尝试每试一个边长就跑一次 check直到第一次成功为止。这样虽然简单但效率太低而且没有必要。这里的关键观察是单调性边长越大矩形越容易放进去。想想看side变大之后几个条件都只会变得更宽松。单个矩形宽度大于side或高度大于side的特判更难触发换行条件里的cur_w width side也更难满足结算时used_h side更不容易成立。总之一旦某个边长可行所有比它更大的边长都一定可行。反过来如果某个边长不可行所有比它更小的边长也一定不可行。这就是标准的二分答案模型我们不是在数组里二分查找某个值而是在一个从“不可行”到“可行”的单调序列上找第一个可行的点。题面给了你一个天然的范围我们可以在这个范围上直接二分。3.2 左右边界这样取二分一次过二分的边界是有讲究的取不好轻则多跑几轮重则死循环或者答案错误。左边界lo不能取 0因为答案至少不能小于所有矩形的最大宽度和最大高度。宽度最大那个矩形一旦横跨整行边长小于它的宽度就永远放不下高度最大那个矩形只要作为某一行出现这一行自身的高度就占掉了至少这么多垂直空间。所以lo max(所有矩形的最大宽度, 所有矩形的最大高度)。右边界hi要保证一定可行。一个最简单的可行方案是每个矩形单独占一行。这样总行数就是矩形数量每一行的高度是矩形自身的高度所有行的高度加起来是sum(height)而每一行的宽度最多不会超过max(width)。所以只要边长取max(sum(height), max(width))就一定能按规则放完。这个上界既不松到离谱又足够安全。二分写法用最常见的“左闭右开”思路计算mid (lo hi) // 2。如果can_place(mid)为真说明mid可行那么答案可能是mid或更小收缩右边界hi mid。如果can_place(mid)为假说明mid太小答案一定大于mid收缩左边界lo mid 1。当lo hi时这个值就是最小可行边长。3.3 完整代码与复杂度def can_place(side, sizes): used_h 0 cur_w 0 cur_h 0 for wi, hi in sizes: if wi side or hi side: return False if cur_w 0: cur_h hi elif hi ! cur_h or cur_w wi side: used_h cur_h cur_w 0 cur_h hi cur_w wi if cur_w: used_h cur_h return used_h side def min_side(sizes): if not sizes: return 0 max_w max(w for w, _ in sizes) max_h max(h for _, h in sizes) sum_h sum(h for _, h in sizes) lo max(max_w, max_h) hi max(sum_h, max_w) while lo hi: mid (lo hi) // 2 if can_place(mid, sizes): hi mid else: lo mid 1 return lo这段代码的核心就是can_place二分部分完全是模板。时间复杂度是O(n log S)其中n是矩形数量S是二分上界和下界的差值。就算矩形数量很多这个复杂度在周赛第一题的范围内也完全够用。重点是这种做法不需要维护任何复杂的数据结构空间复杂度是O(1)。如果你最终只需要判断给定的side是否能放下那就直接调用can_place(side, sizes)连二分都不用写。但如果题目要求的是最小边长上面这个二分会自动帮你在可行区间里锁定答案。4. 周赛实战第一题要形成解题肌肉记忆4.1 先写判断函数再决定要不要二分很多人在周赛第一题上的心态是“越快提交越好”结果往往是被一两分钟的急躁坑掉大量罚时。我的建议是拿到这种“能否放得下”的题先不要急着套二分而是先把can_place写到草稿纸上。这一步的目的是把题目的约束翻译成代码逻辑。你在草稿纸上画的变量越清晰后面写代码就越不容易乱。我在周赛里通常会在草稿上画一个坐标系横轴是宽度纵轴是高度当前行底边在used_h处然后手推一个简单样例比如[[2,1],[2,1]]确认边界条件能跑通再上编辑器敲代码。先写判断函数还有一个好处如果你一开始直接写二分逻辑上等于把两个问题混在一起。到时候分不清是判断函数写错了还是二分边界写错了排查成本会翻倍。先让判断函数独立跑通再把它当黑盒喂给二分思路会异常清晰。4.2 和“爱吃香蕉的狒狒”共用一套解题模板如果你熟悉经典题“爱吃香蕉的狒狒”LeetCode 875你可能会发现这两道题的骨架几乎是同一个。“爱吃香蕉的狒狒”给定香蕉堆和总时间求最小速度使得按照每小时最多吃一堆、一堆不够就多花一小时吃掉这一堆的规则能在限定时间内吃完。它做的是写一个can_finish(speed)判断总耗时是否小于等于给定时间然后二分速度。速度越大越容易吃完正好是单调的。“分割正方形 I”给定矩形序列求最小边长使得按规则能全部放下。它做的是写一个can_place(side)判断是否能放完然后二分边长。边长越大越容易放下同样单调。这两个题放在一起看就是一个完整的模板找一个与限制条件相关的目标量写一个关于这个目标量的可行性判断函数然后二分找最小或最大可行值。周赛和热门题里大量出现这种模式比如在限定天数内送完包裹、在限定时间内复制文件、给机器人分配任务等等全是这个套路。所以我一直建议准备周赛不要只看题号而要整理“题型模板”。像这种“二分答案 可行性函数”的模板比背一百道具体题目的解法更有用。每次遇到新题先想这个问题的限制条件单调吗如果单调那就把可行性函数写好二分水到渠成。4.3 本地对拍怎么验证明天不会翻车写完算法之后光靠样例通过是不够的。我自己有一个习惯会写一个非常暴力的朴素版本和二分版本做对拍。比如在这道题里朴素版本可以写成从lo开始for side in range(lo, hi 1)逐一调用can_place返回第一个成功的边长。这个版本没有任何二分逻辑纯粹靠枚举正确性一眼可见。然后用随机生成器造一堆数据比如随机生成 0 到 20 个矩形宽高随机在 1 到 30 之间把两个版本的结果对比。对拍如果跑到几千组数据都一致那基本可以放心提交。这个方法我每次打周赛前都会用来验证模板题时间成本不高但能避免大量低级错误。特别是第一题你越是想快速提交越应该用对拍给自己兜底。5. 我踩过的坑常见问题与排查实录5.1 换行时高度漏算这个坑我印象太深了第一次做类似题目时我的循环结束直接return True结果复杂样例全部翻车。原因就是我把“换行结算旧行”写在了换行分支里但最后一行的旧行没有机会被换行触发于是它的高度从未被加进used_h。排查方法很简单在循环结束后打印used_h和cur_h你会发现最后一行高度确实没加上。解决方式也简单就是循环结束后补一句“如果当前行还有内容就结算”。我习惯写if cur_w: used_h cur_h但也可以一开始就把逻辑设计成“每开新行就先结算旧行”这样就不用额外补。5.2 单个矩形比正方形还宽can_place里如果不加单矩形超宽判断会发生什么当cur_w 0时代码会直接设cur_h然后累加宽度根本不会触发换行分支。比如side 5来了一个宽度为 100 的矩形它会被糊里糊涂地算进当前行最后宽度变量变成 100但函数可能返回True因为它没意识到 100 已经超出可容纳范围了。这也是为什么我坚持把if wi side or hi side放在循环体最前面。它不只是一个防御性代码它是在模拟场景里最真实的一票否决一个矩形比整个容器还大那就没有任何继续讨论的必要。高度同理虽然高度超限不一定会立刻触发失败但尽早返回可以避免后面出现各种匪夷所思的中间状态。5.3 二分不收敛二分模板如果写成if can_place(mid): lo mid else: hi mid - 1在求“最小可行值”的场景下必出问题。因为当mid可行时你不敢确定mid是不是答案你只能把右边界往中间收而不能直接让lo跑到mid上去。正确的记忆方式是四个字可行收缩。可行就把右边界收到mid不可行就把左边界移到mid 1。这个模板对应的最终状态是lo hi它就是答案。写错的人基本都是把lo mid 1和hi mid - 1用反了。建议不用“开区间”“闭区间”这种容易搞混的说法直接在注释里写清楚“哪边可行就收哪边”。5.4 顺手排序导致 WA这题的输入顺序就是摆放顺序排序会破坏题意。我不止一次看到有人一上来就按宽度或者高度排序因为他下意识觉得“先放大的后放小的能塞得更满”。但在这种题里顺序是由测试数据给定的不是由你决定的排序后的模拟结果哪怕再完美也不是题目要求的答案。如果你发现自己想排序说明还是在把它当成背包问题或贪心题。回到题目描述里找“按给定顺序”这几个字。这类题要么是模拟题要么是二分答案题无论如何都不该排序。5.5 快速自查清单我把容易踩的坑整理成一个表每次写完都可以对着过一遍现象可能原因处理方式看起来能放下但函数返回 False换行时把旧行高度加错位置每次开新行或结束行时统一结算函数返回 True 但实际上放不下最后一行高度没结算循环结束后补used_h cur_h单矩形超宽却通过了判断cur_w 0时不触发换行循环开头判断wi side或hi side二分结果偏大或死循环可行分支位置写错使用if can_place(mid): hi mid else: lo mid 1同一组数据不同顺序答案不同引入排序破坏了输入顺序严格按sizes顺序遍历不要重排边界变量崩溃sizes为空时调用max()在函数开头处理空数组这六条基本覆盖了这道题 90% 的编写错误。每次提交前看一眼这个表能省下不少罚时。这道题我自己实际做的时候第一次也栽在最后一行漏算上后来养成了“换行结算旧行、循环结束补最后一行”的习惯这类布局模拟题就再也没出过问题。后来我做更多的二分答案题发现绝大多数题的核心难点都集中在那个判断函数上二分反而是最好写的部分。所以我的建议很直接遇到这类问题先花心思把can_place敲到稳再把二分模板套上去。判断函数就像地基地基正了上面的二分才不会歪。这道题刷完你收获的不仅是一道题的题解更是一整套可以复用在周赛第一题上的解题套路。