LC 1725. 可以形成最大正方形的矩形数目

题目描述

这是 LeetCode 上的 1725. 可以形成最大正方形的矩形数目 ，难度为 简单。

给你一个数组 rectangles，其中 $rectangles[i] = [l_i, w_i]$ 表示第 $i$ 个矩形的长度为 $l_i$ 、宽度为 $w_i$ 。

如果存在 k 同时满足 $k <= l_i$ 和 $k <= w_i$ ，就可以将第 i 个矩形切成边长为 k 的正方形。例如，矩形 $[4,6]$ 可以切成边长最大为 $4$ 的正方形。

设 maxLen 为可以从矩形数组 rectangles 切分得到的 最大正方形 的边长。

请你统计有多少个矩形能够切出边长为 maxLen 的正方形，并返回矩形 数目 。

示例 1：

输入：rectangles = [[5,8],[3,9],[5,12],[16,5]]

输出：3

解释：能从每个矩形中切出的最大正方形边长分别是 [5,3,5,5] 。
最大正方形的边长为 5 ，可以由 3 个矩形切分得到。

示例 2：

输入：rectangles = [[2,3],[3,7],[4,3],[3,7]]

输出：3

提示：

• $1 <= rectangles.length <= 1000$
• $rectangles[i].length == 2$
• $1 <= li, wi <= 10^9$
• $li != wi$

---

模拟

根据题意，对于任意一个矩形 $rectangles[i]$ 而言，其能分割出的最大方形边长为 $\min(rectangles[i][0], rectangles[i][1])$。

我们在遍历过程中使用变量 max 维护最大边长，同时使用 ans 记录能够分割出最大边长 max 的矩形数量。

代码：

class Solution {
    public int countGoodRectangles(int[][] rectangles) {
        int max = 0, ans = 0;
        for (int[] r : rectangles) {
            int cur = Math.min(r[0], r[1]);
            if (cur == max) ans++;
            else if (cur > max) {
                max = cur; ans = 1;
            }
        }
        return ans;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1725 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。