number-of-rectangles-that-can-form-the-largest-square

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array <code>rectangles</code> where <code>rectangles[i] = [li, wi]</code> represents the <code>ith</code> rectangle of length <code>li</code> and width <code>wi</code>.

You can cut the <code>ith</code> rectangle to form a square with a side length of <code>k</code> if both <code>k &lt;= li</code> and <code>k &lt;= wi</code>. For example, if you have a rectangle <code>[4,6]</code>, you can cut it to get a square with a side length of at most <code>4</code>.

Let <code>maxLen</code> 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 <code>maxLen</code>.

&nbsp;
Example 1:

<pre>
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.
</pre>

Example 2:

<pre>
Input: rectangles = [[2,3],[3,7],[4,3],[3,7]]
Output: 3
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= rectangles.length &lt;= 1000</code></li>
	<li><code>rectangles[i].length == 2</code></li>
	<li><code>1 &lt;= li, wi &lt;= 109</code></li>
	<li><code>li != wi</code></li>
</ul>

countGoodRectangles

Number Of Rectangles That Can Form The Largest Square

Array

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

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

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

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

 

示例 1：

<pre>
输入：rectangles = [[5,8],[3,9],[5,12],[16,5]]
输出：3
解释：能从每个矩形中切出的最大正方形边长分别是 [5,3,5,5] 。
最大正方形的边长为 5 ，可以由 3 个矩形切分得到。
</pre>

示例 2：

<pre>
输入：rectangles = [[2,3],[3,7],[4,3],[3,7]]
输出：3
</pre>

 

提示：

<ul>
	<li><code>1 <= rectangles.length <= 1000</code></li>
	<li><code>rectangles[i].length == 2</code></li>
	<li><code>1 <= li, wi <= 109</code></li>
	<li><code>li != wi</code></li>
</ul>