A.每日一题——2975. 移除栅栏得到的正方形田地的最大面积

题目链接：2975. 移除栅栏得到的正方形田地的最大面积（中等）

算法原理：

解法：暴力枚举

622ms击败78.57%

时间复杂度O(N²)

此题跟上一题 A.每日一题——2943. 最大化网格图中正方形空洞的面积 的不同点👇

空洞面积题：给的可移除线条数组外的内部线条依然存在，且固定

田地面积题（此题）：除了给的可移除栅栏数组外，没有其他内部栅栏，只剩下四周不可变的栅栏了

也就是说，空洞面积题不存在无解情况，最小的正方形是1×1的，而田地面积题因内部栅栏的分布可能造成无解情况，所以这时需要返回-1

这些区别也就是为什么此题不能直接沿用上一题代码的原因

此题的解题方法👇

①分别求出水平栅栏和垂直栅栏的间隙集合，枚举水平栅栏间隙集合，看垂直栅栏集合能否与之构成正方形，能的话就逐步更新取最大值

②由于间隙出现一次即可，所以用Set容器天然去重能够减少遍历次数

③求间隙过程中，由于四周最外围的栅栏不能移除，所以求间隙的时候必须参与运算，那要怎样算进去呢？

可以创建一个临时数组，遍历这个临时数组，逐步计算间隙存进哈希表，咱就可以在遍历前把这两个边界扔进临时数组，排个序就能正常求间隙了

比如网格高度 m=5，水平围栏 hFences=[2,4]，临时数组先把数组扩展成 [2,4,1,5]，然后排序成 [1,2,4,5]。接下来两两算差：2-1=1，4-1=3，5-1=4，4-2=2，5-2=3，5-4=1，这些差值（1,2,3,4）就是水平方向所有可能的边长，最后存到集合里返回

Java代码：

class Solution { public int maximizeSquareArea(int m, int n, int[] hFences, int[] vFences) { final int MOD=1_000_000_007; //获取水平方向所有可能的间隔长度集合 Set<Integer> hSet=f(hFences,m); //获取垂直方向所有可能的间隔长度集合 Set<Integer> vSet=f(vFences,n); int ret=0; //遍历水平方向的所有间隔长度 for(int x:hSet) //如果垂直方向也存在相同的间隔长度，说明可以围成边长为x的正方形 if(vSet.contains(x)) //更新最大边长 ret=Math.max(ret,x); return ret>0?(int)((long)ret*ret%MOD):-1; } private Set<Integer> f(int[] a,int l){ //获取原栅栏数组的长度 //比如水平围栏hFences=[2,4],m=5 int n=a.length; //复制原数组并扩容两个位置，存储两个边界点1和l //先扩容成[2,4,0,0] a=Arrays.copyOf(a,n+2); //存储起始坐标，最左最上边界 //变成[2,4,1,0] a[n++]=1; //存储结束坐标，最右最下边界 //变成[2,4,1,5] a[n++]=l; //一起排序，保证差值为正 //变成[1,2,4,5] Arrays.sort(a); //计算a中任意两个数的差，存到哈希表中 Set<Integer> set=new HashSet<>(); for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) set.add(a[j]-a[i]); return set; } }