企业官网建设流程全解析

昨儿周赛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 = 0，cur_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 = 2，cur_w = 4。
• 第三个矩形[4,2]：高度相等，但cur_w + 4 = 8 > 6，宽度放不下，又触发换行。结算used_h = 3，开新行cur_h = 2，cur_w = 4。
• 第四个矩形[4,2]：同样高度相等但宽度放不下，再次换行。结算used_h = 5，开新行cur_h = 2，cur_w = 4。
• 循环结束，最后一行还没结算，补上used_h += 2 = 7，7 大于 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 快速自查清单

我把容易踩的坑整理成一个表，每次写完都可以对着过一遍：

这六条基本覆盖了这道题 90% 的编写错误。每次提交前看一眼这个表，能省下不少罚时。

这道题我自己实际做的时候，第一次也栽在最后一行漏算上，后来养成了“换行结算旧行、循环结束补最后一行”的习惯，这类布局模拟题就再也没出过问题。后来我做更多的二分答案题，发现绝大多数题的核心难点都集中在那个判断函数上，二分反而是最好写的部分。所以我的建议很直接：遇到这类问题，先花心思把can_place敲到稳，再把二分模板套上去。判断函数就像地基，地基正了，上面的二分才不会歪。这道题刷完，你收获的不仅是一道题的题解，更是一整套可以复用在周赛第一题上的解题套路。