492. 构造矩形

Easy

题目描述

一个网页开发者需要知道如何设计网页的尺寸。现在，给定一个特定矩形网页的面积，你的任务是设计一个矩形网页，其长度 L 和宽度 W 满足以下要求：

• 你设计的矩形网页必须等于给定的目标面积。
• 宽度 W 不应大于长度 L，即 L >= W。
• 长度 L 和宽度 W 之间的差应该尽可能小。

返回一个数组 [L, W]，其中 L 和 W 是你设计的网页的长度和宽度。

示例 1：

输入：area = 4
输出：[2,2]
解释：目标面积是 4，构造它的所有可能方式是 [1,4]、[2,2]、[4,1]。
但根据要求 2，[1,4] 是非法的；根据要求 3，与 [2,2] 相比，[4,1] 不是最优的。所以长度 L 是 2，宽度 W 是 2。

示例 2：

输入：area = 37
输出：[37,1]

示例 3：

输入：area = 122122
输出：[427,286]

约束：

• 1 <= area <= 10^7

解题思路

这道题要求我们找到一个矩形的长和宽，使得面积等于给定值，同时满足长大于等于宽，且它们的差尽可能小。

核心思路： 为了让 L 和 W 的差尽可能小，我们希望找到最接近正方形的矩形。对于面积为 area 的矩形，如果是正方形，那么边长就是 √area。

算法步骤：

1. 从 √area 开始向下搜索，找到第一个能整除 area 的数作为宽度 W
2. 对应的长度 L = area / W
3. 由于我们从 √area 开始向下搜索，找到的第一个因子必然满足 W ≤ L 且差值最小

为什么从 √area 开始？

• 如果 W > √area，那么 L = area/W < √area，这样就不满足 L ≥ W 的条件
• 所以 W 的最大可能值就是 √area
• 从 √area 开始向下搜索，找到的第一个因子就是最优解

这种方法的时间复杂度是 O(√area)，空间复杂度是 O(1)。

代码实现

class Solution {
public:
    vector<int> constructRectangle(int area) {
        int w = sqrt(area);
        while (area % w != 0) {
            w--;
        }
        return {area / w, w};
    }
};

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

public class Solution {
    public int[] ConstructRectangle(int area) {
        int w = (int)Math.Sqrt(area);
        while (area % w != 0) {
            w--;
        }
        return new int[] {area / w, w};
    }
}

var constructRectangle = function(area) {
    let w = Math.floor(Math.sqrt(area));
    while (area % w !== 0) {
        w--;
    }
    return [Math.floor(area / w), w];
};

复杂度分析