题目描述
这是 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 原题链接和其他优选题解。
