移除栅栏得到的正方形田地的最大面积

There is a large (m - 1) x (n - 1) rectangular field with corners at (1, 1) and (m, n) containing some horizontal and vertical fences given in arrays hFences and vFences respectively.

Horizontal fences are from the coordinates (hFences[i], 1) to (hFences[i], n) and vertical fences are from the coordinates (1, vFences[i]) to (m, vFences[i]).

Return the maximum area of a square field that can be formed by removing some fences (possibly none) or -1 if it is impossible to make a square field.

Since the answer may be large, return it modulo 109 + 7.

Note: The field is surrounded by two horizontal fences from the coordinates (1, 1) to (1, n) and (m, 1) to (m, n) and two vertical fences from the coordinates (1, 1) to (m, 1) and (1, n) to (m, n). These fences cannot be removed.

 

Example 1:

Input: m = 4, n = 3, hFences = [2,3], vFences = [2]
Output: 4
Explanation: Removing the horizontal fence at 2 and the vertical fence at 2 will give a square field of area 4.

Example 2:

Input: m = 6, n = 7, hFences = [2], vFences = [4]
Output: -1
Explanation: It can be proved that there is no way to create a square field by removing fences.

 

Constraints:

• 3 <= m, n <= 109
• 1 <= hFences.length, vFences.length <= 600
• 1 < hFences[i] < m
• 1 < vFences[i] < n
• hFences and vFences are unique.

// 思路：
// 1. 使用Java Stream对水平和垂直栅栏排序，并找到每一块区域的最大边长。
// 2. 通过计算最大正方形边长来判断结果。
// 3. 返回最大正方形的面积，如果没有则返回-1。
// 注意：取余 10^9 + 7

import java.util.*;
import java.util.stream.*;

public class Solution {
    public int maxSquareArea(int m, int n, int[] hFences, int[] vFences) {
        Arrays.sort(hFences);
        Arrays.sort(vFences);

        int maxHGap = Math.max(hFences[0] - 1, m - hFences[hFences.length - 1]);
        int maxVGap = Math.max(vFences[0] - 1, n - vFences[vFences.length - 1]);

        maxHGap = IntStream.range(1, hFences.length)
                .map(i -> hFences[i] - hFences[i - 1] - 1)
                .reduce(maxHGap, Math::max);

        maxVGap = IntStream.range(1, vFences.length)
                .map(i -> vFences[i] - vFences[i - 1] - 1)
                .reduce(maxVGap, Math::max);

        int maxSide = Math.min(maxHGap, maxVGap);
        if (maxSide == 0) return -1;

        long area = (long) maxSide * maxSide % (1000000007);
        return (int) area;
    }
}

此题解的思路是首先对水平栅栏和垂直栅栏的坐标进行排序，并在两个数组的开始和结尾分别添加边界栅栏的坐标。然后，通过双重循环遍历所有可能的正方形的大小，对于每个大小，检查是否存在对应的水平栅栏和垂直栅栏组合来形成一个正方形。这是通过在一个集合中存储所有垂直栅栏间距的唯一值，并在遍历水平栅栏时检查该集合中是否存在与当前水平栅栏间距相等的值来实现的。如果找到这样的组合，则更新最大正方形的边长。最后，返回最大正方形的面积。

O(h log h + v log v + v^2 + h^2)

O(h + v + v^2)