题目描述
有一个大型的 (m - 1) x (n - 1)
矩形田地,其两个对角分别是 (1, 1)
和 (m, n)
,田地内部有一些水平栅栏和垂直栅栏,分别由数组 hFences
和 vFences
给出。
水平栅栏为坐标 (hFences[i], 1)
到 (hFences[i], n)
,垂直栅栏为坐标 (1, vFences[i])
到 (m, vFences[i])
。
返回通过 移除 一些栅栏(可能不移除)所能形成的最大面积的 正方形 田地的面积,或者如果无法形成正方形田地则返回 -1
。
由于答案可能很大,所以请返回结果对 10^9 + 7
取余 后的值。
注意:田地外围两个水平栅栏(坐标 (1, 1)
到 (1, n)
和坐标 (m, 1)
到 (m, n)
)以及两个垂直栅栏(坐标 (1, 1)
到 (m, 1)
和坐标 (1, n)
到 (m, n)
)所包围。这些栅栏 不能 被移除。
样例
输入:m = 4, n = 3, hFences = [2,3], vFences = [2]
输出:4
解释:移除位于 2 的水平栅栏和位于 2 的垂直栅栏将得到一个面积为 4 的正方形田地。
输入:m = 6, n = 7, hFences = [2], vFences = [4]
输出:-1
解释:可以证明无法通过移除栅栏形成正方形田地。
限制
3 <= m, n <= 10^9
1 <= hFences.length, vFences.length <= 600
1 < hFences[i] < m
1 < vFences[i] < n
hFences
和vFences
中的元素是唯一的。
算法
(暴力枚举,哈希表) $O(hFences.length^2 + vFences.length^2)$
- 暴力枚举所有
hFences
可以产生的高度,存入哈希表。 - 然后暴力枚举所有
vFences
可以产生的宽度,如果哈希表中存在,更新答案。
时间复杂度
- 暴力枚举
hFences
和vFences
可以产生的高度和宽度时间复杂度为 $O(hFences.length^2 + vFences.length^2)$,且单次存储和读取哈希表的时间复杂度为常数,故总时间复杂度为 $O(hFences.length^2 + vFences.length^2)$。
空间复杂度
- 需要 $O(hFences.length^2)$ 的额外时间存储哈希表。
C++ 代码
#define LL long long
class Solution {
public:
int maximizeSquareArea(int m, int n, vector<int>& hFences, vector<int>& vFences) {
const int mod = 1000000007;
hFences.push_back(1);
hFences.push_back(m);
vFences.push_back(1);
vFences.push_back(n);
unordered_set<int> seen;
for (int i = 0; i < hFences.size(); i++)
for (int j = i + 1; j < hFences.size(); j++)
seen.insert(abs(hFences[i] - hFences[j]));
LL ans = -1;
for (int i = 0; i < vFences.size(); i++)
for (int j = i + 1; j < vFences.size(); j++) {
int x = abs(vFences[i] - vFences[j]);
if (seen.find(x) != seen.end())
ans = max(ans, (LL)(x) * x);
}
return ans % mod;
}
};