LeetCode1725.可以形成最大正方形的矩形数目题解

1725、可以形成最大正方形的矩形数目题解

题目来源：1725、可以形成最大正方形的矩形数目

2022.02.04每日一题

解题思路：一个矩形想要裁成正方形，需要统计其最短边的长度

因此可以统计每个矩形短边的长度，寻找最大值，每次遇见与最大值相同的边，结果加一，若遇见比现有最大值还要大的，则重置

详细代码以及注解如下

C++版本

class Solution {public: int countGoodRectangles(vector> &rectangles) { // 统计当前数量 int res = 0; // 记录当前的最大值 int Max = 0; // 遍历数组，寻找极值 for (vector re: rectangles) { // 若 Max 不是当前最大值，则更新 Max，并重置 res if (Max < (re[0] > re[1] ? re[1] : re[0])) { Max = (re[0] > re[1] ? re[1] : re[0]); res = 1; } // 判断当前矩形的值与当前Max的值是否相等，若相等则结果加一 else if (Max == (re[0] > re[1] ? re[1] : re[0])) { res++; } } // 返回结果 return res; }};

Java版本

class Solution { public int countGoodRectangles(int[][] rectangles) { // 记录当前的最大值 int Max = 0; // 统计当前数量 int res = 0; // 遍历数组，寻找极值 for (int[] re : rectangles) { // 若 Max 不是当前最大值，则更新 Max，并重置 res if (Max < Math.min(re[0], re[1])) { Max = Math.min(re[0], re[1]); res = 1; } // 判断当前矩形的值与当前Max的值是否相等，若相等则结果加一 else if (Max == Math.min(re[0], re[1])) { res++; } } // 返回结果 return res; }}

时间复杂度O(n)

空间复杂度O(1)