1725. 可以形成最大正方形的矩形数目 : 简单模拟题

题目描述

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

Tag : 「模拟」

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

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

设 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 <= 10001<=rectangles.length<=1000
• rectangles[i].length == 2rectangles[i].length==2
• 1 <= li, wi <= 10^91<=li,wi<=109
• li != wili!=wi

模拟

根据题意，对于任意一个矩形 rectangles[i]rectangles[i] 而言，其能分割出的最大方形边长为 \min(rectangles[i][0], rectangles[i][1])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(n)
• 空间复杂度：O(1)O(1)

最后

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

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

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

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