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

LeetCode 1725. 可以形成最大正方形的矩形数目题解 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)