题目
有一个大型的 (m - 1) x (n - 1) 矩形田地，其两个对角分别是 (1, 1) 和 (m, n) ，田地内部有一些水平栅栏和垂直栅栏，分别由数组 hFences 和 vFences 给出。
水平栅栏为坐标 (hFences[i], 1) 到 (hFences[i], n)，垂直栅栏为坐标 (1, vFences[i]) 到 (m, vFences[i]) 。
返回通过 移除 一些栅栏（可能不移除）所能形成的最大面积的 正方形 田地的面积，或者如果无法形成正方形田地则返回 -1。
由于答案可能很大，所以请返回结果对 109 + 7 取余 后的值。
注意：田地外围两个水平栅栏（坐标 (1, 1) 到 (1, n) 和坐标 (m, 1) 到 (m, n) ）以及两个垂直栅栏（坐标 (1, 1) 到 (m, 1) 和坐标 (1, n) 到 (m, n) ）所包围。这些栅栏 不能 被移除。
示例 1：
输入：m = 4, n = 3, hFences = [2,3], vFences = [2]
输出：4
解释：移除位于 2 的水平栅栏和位于 2 的垂直栅栏将得到一个面积为 4 的正方形田地。
示例 2：
输入：m = 6, n = 7, hFences = [2], vFences = [4]
输出：-1
解释：可以证明无法通过移除栅栏形成正方形田地。
提示：
3 <= m, n <= 109 1 <= hFences.length, vFences.length <= 600 1 < hFences[i] < m 1 < vFences[i] < n hFences 和 vFences 中的元素是唯一的。
Problem: https://leetcode.cn/problems/maximum-squar100169 e-area-by-removing-fences-from-a-field/description/
[TOC]
思路
遍历所有的横向栏杆与纵向栏杆，算出横向栏杆之间的差和纵向栏杆之间的差并存储两个集合，最终的答案就是两个集合的交集的平方
复杂度
O(m^2+n^2)
O(m+n)
Code
class Solution: def maximizeSquareArea(self, m: int, n: int, hFences: List[int], vFences: List[int]) -> int: ans = -1 hFences.append(m) hFences.insert(0,1) row = set() for i in range(len(hFences)): for j in range(0,i): row.add(abs( hFences[i] - hFences[j] )) vFences.append(n) vFences.insert(0,1) col = set() for i in range(len(vFences)): for j in range(0,i): col.add(abs(vFences[i] - vFences[j])) if abs(vFences[i] - vFences[j]) in row : ans = max(ans,pow(abs(vFences[i] - vFences[j]),2)) for val in row: if val in col: ans = max(ans,pow(val,2)) return ans % 1_000_000_007 if
