企业官网建设流程全解析

• 教程
• 文档

本文是「刷穿 LeetCode」系列第 492 篇题解的深度展开。作为 Web 开发者，规划页面尺寸时经常需要在面积固定的前提下找到长宽最接近的布局方案。本文将从题目约束出发，推导"从平方根向下枚举"的核心思路，给出完整可运行的代码，并结合当前仓库（LogicStack-LeetCode）中模拟算法索引体系，分析这类"模拟 + 枚举"题型的通用套路与易错点。读完本文，你将掌握如何在 $O(\sqrt{n})$ 时间内解决此类"固定面积求最接近长宽比"问题。

一、题目背景：为什么 Web 开发者需要这道题

LeetCode492. 构造矩形（Construct the Rectangle，难度：简单）是一道非常贴近工程实践的题目。作为一位 Web 开发者，懂得规划页面尺寸是基本素养：给定一个具体的矩形页面面积，需要设计出长度L和宽度W，并且同时满足以下三条硬性要求：

1. 面积守恒：设计的矩形页面面积必须等于给定的目标面积，即 $L \times W = area$；
2. 方向约定：宽度W不应大于长度L，即 $L \ge W$；
3. 接近最优：长度L和宽度W之间的差距应当尽可能小，即最小化 $|L - W|$。

最终需要按顺序输出[L, W]。

这道题在仓库中被收录于 Index/模拟.md 索引表，Tag 为「模拟」，难度标记为简单，推荐指数为 🤩🤩🤩🤩，属于典型的基础模拟枚举题。

示例解析

输入: 4 输出: [2, 2] 解释: 目标面积是 4，所有可能的构造方案有 [1,4], [2,2], [4,1]。 但是根据要求 2，[1,4] 不符合要求; 根据要求 3，[2,2] 比 [4,1] 更能符合要求。 所以输出长度 L 为 2，宽度 W 为 2。

数据范围说明

• 给定的面积不大于 10,000,000 且为正整数；
• 设计出的页面长度和宽度必须都是正整数。

数据上限 $10^7$ 意味着 $\sqrt{area}$ 最多约为 $3162$，这直接决定了"枚举所有可能因子"这种朴素做法的可行性。

二、问题建模：把三条要求翻译成算法语言

在动笔写代码之前，先把三条约束翻译成可计算的数学条件：

由约束 1 可知，$L$ 与 $W$ 互为因子对（即 $W = area / L$，且 $area \bmod L = 0$）。因此问题的本质是：在 $area$ 的所有正整数因子对中，找到乘积等于 $area$、且两者差值最小的一组。

进一步观察可以提炼出两个关键性质：

• 因子对必然成对出现：如果 $d$ 是 $area$ 的因子，那么 $area / d$ 也是因子；
• 因子对中较小的那个一定不超过$\sqrt{area}$。因为若 $W > \sqrt{area}$，则 $L = area / W < \sqrt{area}$，两者地位互换即可。

基于第二条性质，$L \ge W$ 意味着我们只需要在区间 $[1, \sqrt{area}]$ 中寻找满足 $area \bmod W = 0$ 的最大宽度 $W$，此时对应的长度 $L = area / W$ 自然满足 $L \ge W$。

三、核心思路：从 √area 向下枚举，命中即答案

原题解给出的模拟策略非常精炼：从 $\sqrt{area}$ 开始向下模拟，遇到的第一个能够被整除的数值，就是最优宽度，直接返回答案。

class Solution { public int[] constructRectangle(int area) { for (int i = (int)(Math.sqrt(area)); ;i--) { if (area % i == 0) return new int[]{area / i, i}; } } }

为什么"从 $\sqrt{area}$ 向下找到的第一个可整除的数"就是最优解？原因在于单调性：

• 宽度 $W$ 越接近 $\sqrt{area}$，长度 $L = area / W$ 就越接近 $W$，两者差值 $|L - W|$ 就越小；
• 从 $\sqrt{area}$ 向下枚举，遇到的是所有可行宽度中的最大值（也就是最接近 $\sqrt{area}$ 的那个），对应的 $L$ 自然最小且满足 $L \ge W$；
• 因此第一次命中area % i == 0时，该 $(L, W)$ 组合的差值必然已经最小，无需继续枚举。

这个枚举过程至多扫描 $\sqrt{area}$ 个数（实际命中点通常远早于此），因此时间复杂度为 $O(\sqrt{n})$，空间上只使用常数个变量，为 $O(1)$。

多语言等价实现

原题解以 Java 给出。当前仓库的题解风格（可参考同目录下的 495. 提莫攻击，它同时提供了 Java / C++ / Python / TypeScript 四种版本）表明同一逻辑可以方便地移植到其他主流语言。以下实现与上述 Java 逻辑完全一致，可直接运行验证：

class Solution { public: vector<int> constructRectangle(int area) { for (int i = (int)sqrt(area); ; i--) { if (area % i == 0) return {area / i, i}; } } };

class Solution: def constructRectangle(self, area: int) -> List[int]: i = int(area ** 0.5) while True: if area % i == 0: return [area // i, i] i -= 1

function constructRectangle(area: number): number[] { for (let i = Math.floor(Math.sqrt(area)); ; i--) { if (area % i === 0) return [area / i, i]; } }

四、边界情况与易错点分析

4.1 浮点开方精度问题

Math.sqrt(area)返回的是double，强制转换为int时是向下取整。由于我们接下来是向下枚举而不是向上，向下取整天然是安全的：真正的最优宽度必然 $\le \sqrt{area}$，从略小的整数起步不会跳过答案。这避免了因浮点误差导致起点比真实 $\sqrt{area}$ 大 1 的隐患。

提示：在 C++ / Python 等语言中使用开方函数时同理，建议始终向下取整后开始枚举，这与"向下找第一个因子"的方向保持一致。

4.2 area = 1 的退化情形

当area = 1时，$\sqrt{1} = 1$，循环第一次判断1 % 1 == 0立即成立，返回[1, 1]。这是唯一满足"面积 = 1 且 L >= W"的整数组合，行为正确，无需额外特判。

4.3 area 为完全平方数

当area = 4（或 9、16 等完全平方数）时，$\sqrt{area}$ 本身即可整除area，第一次循环就返回[√area, √area]，此时 $L = W$，长宽差距为 0，是理论最优。这与题目示例输入: 4 → 输出: [2, 2]完全吻合。

4.4 为什么不需要检查L >= W

由于起点是 $\sqrt{area}$ 的向下取整，枚举过程中i始终 $\le \sqrt{area}$，因此area / i \ge i恒成立，约束 2 自动满足，无需显式判断。

五、正确性证明（三步走）

1. 存在性：$W = 1$ 时必有 $area \bmod 1 = 0$，且 $L = area \ge 1$，因此枚举过程必然在某个 $i \ge 1$ 处终止，循环不会死循环；
2. 可行性：每次命中时都有 $area = L \times i$ 且 $L \ge i$，同时满足约束 1 和约束 2；
3. 最优性：所有候选宽度 $W' \le \sqrt{area}$，且满足整除条件的 $W'$ 构成一个集合。$|L - W| = |area / W - W|$ 在 $W \in (0, \sqrt{area}]$ 上随 $W$ 增大而单调递减，因此集合中最大的 $W'$（即从 $\sqrt{area}$ 向下第一个命中者）对应的差值最小，满足约束 3。

六、题型归类：与仓库中其他「模拟」题的共性

本题在仓库的 Index/模拟.md 索引表中与其他模拟题并列，例如：

• 495. 提莫攻击：按时间序遍历事件，用last记录上一状态的结束点，与本题"向下枚举直到命中"同属顺序遍历 + 状态维护的模拟范式；
• 66. 加一：从最低位向高位模拟进位；
• 412. Fizz Buzz：按规则逐项判定输出；
• 507. 完美数：枚举因子并累加，与本题"枚举因子"的核心操作高度同源。

从这些题可以看出「模拟」类题型的共同特征：题目已经把操作规则描述清楚，解法本质是忠实还原规则 + 选择合适的枚举顺序。本题唯一的"聪明点"在于选择了从 $\sqrt{area}$ 向下而非从 1 向上枚举，从而把因子对的搜索范围压缩了一半，并天然满足 $L \ge W$ 与差值最小两个约束。

七、延伸思考：如果不用开方函数

如果不借助Math.sqrt，还可以用整数二分求出不超过 $\sqrt{area}$ 的最大整数 $r$，再以 $r$ 为起点向下枚举：

class Solution { public int[] constructRectangle(int area) { // 二分定位 sqrt(area) 的整数下界 long lo = 1, hi = area; while (lo < hi) { long mid = (lo + hi + 1) >> 1; if (mid * mid <= area) lo = mid; else hi = mid - 1; } for (int i = (int) lo; ; i--) { if (area % i == 0) return new int[]{area / i, i}; } } }

这种写法用纯整数运算避免了浮点开方的精度问题，且总体复杂度仍为 $O(\log n + \sqrt{n})$。但在本题数据范围（$area \le 10^7$）下，直接使用Math.sqrt已经足够安全，二分方案更多作为思维拓展存在。

八、小结

• 解法本质：在 $[1, \sqrt{area}]$ 内从大到小枚举因子，第一个命中者即为最优宽度；
• 复杂度：时间 $O(\sqrt{n})$，空间 $O(1)$，完全适配 $10^7$ 的数据上限；
• 工程启示：固定面积求最接近长宽比的场景（如页面尺寸规划、图片裁剪比例计算）均可套用"从平方根向两端收缩"的枚举思路；
• 仓库定位：本文对应仓库中的 492. 构造矩形（简单） 题解，同属 模拟 算法专题，读者可结合索引表系统刷完该专题下的其余题目，形成完整的「模拟枚举」方法论。

• 教程
• 文档