★ FEATURED ARTICLE 教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本文是「刷穿 LeetCode」系列第 492 篇题解的深度展开。作为 Web 开发者规划页面尺寸时经常需要在面积固定的前提下找到长宽最接近的布局方案。本文将从题目约束出发推导从平方根向下枚举的核心思路给出完整可运行的代码并结合当前仓库LogicStack-LeetCode中模拟算法索引体系分析这类模拟 枚举题型的通用套路与易错点。读完本文你将掌握如何在 $O(\sqrt{n})$ 时间内解决此类固定面积求最接近长宽比问题。一、题目背景为什么 Web 开发者需要这道题LeetCode492. 构造矩形Construct the Rectangle难度简单是一道非常贴近工程实践的题目。作为一位 Web 开发者懂得规划页面尺寸是基本素养给定一个具体的矩形页面面积需要设计出长度L和宽度W并且同时满足以下三条硬性要求面积守恒设计的矩形页面面积必须等于给定的目标面积即 $L \times W area$方向约定宽度W不应大于长度L即 $L \ge W$接近最优长度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 \times W area$2宽度不超过长度$L \ge W$3长宽差距尽可能小$\minL - W$由约束 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: vectorint 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 - 1function 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 自动满足无需显式判断。五、正确性证明三步走存在性$W 1$ 时必有 $area \bmod 1 0$且 $L area \ge 1$因此枚举过程必然在某个 $i \ge 1$ 处终止循环不会死循环可行性每次命中时都有 $area L \times i$ 且 $L \ge i$同时满足约束 1 和约束 2最优性所有候选宽度 $W \le \sqrt{area}$且满足整除条件的 $W$ 构成一个集合。$|L - W| |area / W - W|$ 在 $W \in (0, \sqrt{area}]$ 上随 $W$ 增大而单调递减因此集合中最大的 $W$即从 $\sqrt{area}$ 向下第一个命中者对应的差值最小满足约束 3。六、题型归类与仓库中其他「模拟」题的共性本题在仓库的 Index/模拟.md 索引表中与其他模拟题并列例如提莫攻击按时间序遍历事件用last记录上一状态的结束点与本题向下枚举直到命中同属顺序遍历 状态维护的模拟范式加一从最低位向高位模拟进位Fizz Buzz按规则逐项判定输出完美数枚举因子并累加与本题枚举因子的核心操作高度同源。从这些题可以看出「模拟」类题型的共同特征题目已经把操作规则描述清楚解法本质是忠实还原规则 选择合适的枚举顺序。本题唯一的聪明点在于选择了从 $\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. 构造矩形简单 题解同属 模拟 算法专题读者可结合索引表系统刷完该专题下的其余题目形成完整的「模拟枚举」方法论。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LogicStack-LeetCode 刷穿系列LeetCode 816 模糊坐标中等枚举与模拟题解LogicStack LeetCode 刷穿系列LeetCode 816 模糊坐标中等枚举与模拟题解 导读 「模糊坐标」Ambiguous Coordi教程文档LogicStack-LeetCode 刷穿系列867. 转置矩阵简单——模拟类题目的第一课LogicStack LeetCode 刷穿系列867. 转置矩阵简单——模拟类题目的第一课 导读 本文基于「宫水三叶的刷题日记」刷穿 LeetCod教程文档AlgoNote 算法通关手册LeetCode 0492 构造矩形题解——从平方根向下枚举因子的数学解法AlgoNote 算法通关手册LeetCode 0492 构造矩形题解——从平方根向下枚举因子的数学解法 导读 本文是「算法通关手册」AlgoNote题库教程文档知识库上一篇Semaphore 密钥仓库实战用 SSH 密钥打通 Ansible Inventory 主机访问TC-012 全流程解析下一篇使用 Xberg 在 Elixir 中提取 HWPX韩文文档内容独立提取实战与源码级解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
阅读完成 · 觉得有帮助？
