Easy

题目描述

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

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

设 maxLen 为你能从任意矩形切出的最大正方形的边长。

请你统计有多少个矩形能够切出边长为 maxLen 的正方形。

示例 1：

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

示例 2：

输入：rectangles = [[2,3],[3,7],[4,3],[3,7]]
输出：3

提示：

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

解题思路

这道题的核心思路非常直观，可以分为两个步骤：

  1. 计算每个矩形能切出的最大正方形边长：对于每个矩形 [length, width]，能切出的最大正方形边长就是 min(length, width)。

  2. 统计能达到最大边长的矩形数量：首先遍历所有矩形，找出所有可能的最大正方形边长中的最大值；然后再次遍历，统计有多少个矩形能达到这个最大值。

算法实现：

  • 第一次遍历：计算每个矩形的最大正方形边长，并记录全局最大值
  • 第二次遍历：统计能达到全局最大值的矩形数量

这种方法的优点是逻辑清晰，代码简洁。虽然需要两次遍历，但时间复杂度仍然是 O(n)，空间复杂度为 O(1)，是最优解法。

也可以用一次遍历的方式实现：在遍历过程中，如果发现更大的边长就更新最大值并重置计数器，如果等于当前最大值就增加计数器。

代码实现

class Solution {
public:
    int countGoodRectangles(vector<vector<int>>& rectangles) {
        int maxLen = 0;
        
        // 找到最大的正方形边长
        for (auto& rect : rectangles) {
            int minSide = min(rect[0], rect[1]);
            maxLen = max(maxLen, minSide);
        }
        
        // 统计能形成最大正方形的矩形数量
        int count = 0;
        for (auto& rect : rectangles) {
            int minSide = min(rect[0], rect[1]);
            if (minSide == maxLen) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
        max_len = 0
        
        # 找到最大的正方形边长
        for rect in rectangles:
            min_side = min(rect[0], rect[1])
            max_len = max(max_len, min_side)
        
        # 统计能形成最大正方形的矩形数量
        count = 0
        for rect in rectangles:
            min_side = min(rect[0], rect[1])
            if min_side == max_len:
                count += 1
        
        return count

public class Solution {
    public int CountGoodRectangles(int[][] rectangles) {
        int maxLen = 0;
        
        // 找到最大的正方形边长
        foreach (int[] rect in rectangles) {
            int minSide = Math.Min(rect[0], rect[1]);
            maxLen = Math.Max(maxLen, minSide);
        }
        
        // 统计能形成最大正方形的矩形数量
        int count = 0;
        foreach (int[] rect in rectangles) {
            int minSide = Math.Min(rect[0], rect[1]);
            if (minSide == maxLen) {
                count++;
            }
        }
        
        return count;
    }
}

/**
 * @param {number[][]} rectangles
 * @return {number}
 */
var countGoodRectangles = function(rectangles) {
    let maxLen = 0;
    let count = 0;
    
    for (let rectangle of rectangles) {
        let squareLen = Math.min(rectangle[0], rectangle[1]);
        if (squareLen > maxLen) {
            maxLen = squareLen;
            count = 1;
        } else if (squareLen === maxLen) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是矩形数组的长度，需要遍历两次数组
空间复杂度O(1)，只使用了常数额外空间