求两矩形交集内最大正方形面积：解法部分用例通过遇瓶颈

给定二维平面中的n个矩形，我们有两个n×2的整数数组bottomLeft和topRight，分别表示第i个矩形的左下角和右上角坐标。需求是找出任意两个矩形交集区域中可形成的最大正方形面积（无交集时返回0）。

以下是仅通过部分测试用例的原Java解法：

class Solution {
    public long largestSquareArea(int[][] bottomLeft, int[][] topRight) {
        int n = bottomLeft.length;
        int maxArea = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int[] intersection = intersect(
                        new int[]{bottomLeft[i][0], bottomLeft[i][1], topRight[i][0], topRight[i][1]},
                        new int[]{bottomLeft[j][0], bottomLeft[j][1], topRight[j][0], topRight[j][1]});
                if (intersection != null) {
                    int sideLength = Math.min(intersection[2] - intersection[0], intersection[3] - intersection[1]);
                    maxArea = Math.max(maxArea, sideLength * sideLength);
                }
            }
        }

        return maxArea;
    }

    private int[] intersect(int[] rect1, int[] rect2) {
        int x1 = Math.max(rect1[0], rect2[0]);
        int y1 = Math.max(rect1[1], rect2[1]);
        int x2 = Math.min(rect1[2], rect2[2]);
        int y2 = Math.min(rect1[3], rect2[3]);
        if (x1 < x2 && y1 < y2) {
            return new int[]{x1, y1, x2, y2};
        }
        return null;
    }
}

问题分析 #

原解法的核心问题是整数溢出：

• maxArea使用int类型存储，当正方形边长超过46340时（46340²为2^31-1，是int类型的最大值），sideLength * sideLength会溢出，导致计算结果错误。
• 每次调用intersect时新建数组属于冗余操作，虽不影响正确性，但会增加不必要的内存开销。

修正后的解法 #

class Solution {
    public long largestSquareArea(int[][] bottomLeft, int[][] topRight) {
        int n = bottomLeft.length;
        long maxArea = 0; // 改用long类型存储面积，避免溢出

        for (int i = 0; i < n; i++) {
            // 提取当前矩形的坐标到局部变量，提升可读性
            int bl1X = bottomLeft[i][0];
            int bl1Y = bottomLeft[i][1];
            int tr1X = topRight[i][0];
            int tr1Y = topRight[i][1];
            
            for (int j = i + 1; j < n; j++) {
                int bl2X = bottomLeft[j][0];
                int bl2Y = bottomLeft[j][1];
                int tr2X = topRight[j][0];
                int tr2Y = topRight[j][1];
                
                // 计算交集的左下角和右上角坐标
                int intersectX1 = Math.max(bl1X, bl2X);
                int intersectY1 = Math.max(bl1Y, bl2Y);
                int intersectX2 = Math.min(tr1X, tr2X);
                int intersectY2 = Math.min(tr1Y, tr2Y);
                
                // 判断是否存在有效交集（宽高均大于0）
                if (intersectX1 < intersectX2 && intersectY1 < intersectY2) {
                    int side = Math.min(intersectX2 - intersectX1, intersectY2 - intersectY1);
                    long currentArea = (long) side * side; // 强制转换为long再相乘，避免溢出
                    if (currentArea > maxArea) {
                        maxArea = currentArea;
                    }
                }
            }
        }

        return maxArea;
    }
}

修正点说明 #

1. 数据类型调整：将maxArea改为long类型，计算面积时先将边长强制转换为long再相乘，彻底避免整数溢出问题。
2. 简化逻辑：移除冗余的intersect方法，直接在循环内计算交集坐标，减少数组创建开销，同时让逻辑更直观。
3. 可读性优化：提取矩形坐标到局部变量，代码结构更清晰。

内容的提问来源于stack exchange，提问作者Akshat Parashar