[LeetCode] 1725. Number Of Rectangles That Can Form The Largest Square

You are given an array rectangles where rectangles[i] = [li, wi] represents the ith rectangle of length li and width wi.

You can cut the ith rectangle to form a square with a side length of k if both k <= li and k <= wi. For example, if you have a rectangle [4,6], you can cut it to get a square with a side length of at most 4.

Let maxLen be the side length of the largest square you can obtain from any of the given rectangles.

Return the number of rectangles that can make a square with a side length of maxLen.

Example 1:

Input: rectangles = [[5,8],[3,9],[5,12],[16,5]]
Output: 3
Explanation: The largest squares you can get from each rectangle are of lengths [5,3,5,5].
The largest possible square is of length 5, and you can get it out of 3 rectangles.

Example 2:

Input: rectangles = [[2,3],[3,7],[4,3],[3,7]]
Output: 3

Constraints:

• 1 <= rectangles.length <= 1000
• rectangles[i].length == 2
• 1 <= li, wi <= 109
• li != wi

可以形成最大正方形的矩形数目。

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

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-rectangles-that-can-form-the-largest-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题意不难理解。对于 input 数组里面给定的每个长方形的长和宽，我们先找到那个宽，这样我们就知道了每个长方形切割之后能形成的最大的正方形的边长，记为 side。在找这个 side 的过程中，我们同时也记录一个全局出现的最大次数 count。如果有某一个 side 的出现次数是 count，那么这个边长即是题意所求。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int countGoodRectangles(int[][] rectangles) {
 3         int max = 0;
 4         int count = 0;
 5         for (int[] rec : rectangles) {
 6             int side = Math.min(rec[0], rec[1]);
 7             if (side > max) {
 8                 max = side;
 9                 count = 1;
10             } else if (side == max) {
11                 count++;
12             }
13         }
14         return count;
15     }
16 }

LeetCode 题目总结