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
Solution: Running Max of Shortest Edge
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: int countGoodRectangles(vector<vector<int>>& rectangles) { int cur = 0; int ans = 0; for (const auto& r : rectangles) { if (min(r[0], r[1]) > cur) { cur = min(r[0], r[1]); ans = 0; } if (min(r[0], r[1]) == cur) ++ans; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment