Description

有一个大型的 (m - 1) x (n - 1) 矩形田地，其两个对角分别是 (1, 1) 和 (m, n) ，田地内部有一些水平栅栏和垂直栅栏，分别由数组 hFences 和 vFences 给出。

水平栅栏为坐标 (hFences[i], 1) 到 (hFences[i], n)，垂直栅栏为坐标 (1, vFences[i]) 到 (m, vFences[i])。

返回通过 移除 一些栅栏（可能不移除）所能形成的最大面积的 正方形 田地的面积，或者如果无法形成正方形田地则返回 -1。

由于答案可能很大，所以请返回结果对 1e9 + 7 取余 后的值。

Constraints

• 3 <= m, n <= 109
• 1 <= hFences.length, vFences.length <= 600
• 1 < hFences[i] < m
• 1 < vFences[i] < n
• hFences 和 vFences 中的元素是唯一的。

Solution

其实就是求最大的 x1 - x2 == y1 - y2。分别 \(O(n^2)\) 求一遍就好了。

只是想展示一下用 std::generator 压扁循环的做法，性能确实是拉完了。

Code

#include <ranges>
#include <generator>

class Solution {
public:
    int maximizeSquareArea(int m, int n, vector<int>& hFences, vector<int>& vFences) {
        hFences.insert(end(hFences), {1, m});
        vFences.insert(end(vFences), {1, n});
        ranges::sort(hFences);
        ranges::sort(vFences);

        unordered_set<int> ydiff;
        int best = 0;

        auto join = [](auto view) -> std::generator<pair<int,int>> {
            for(auto i : views::iota(0uz, size(view))) {
                for(auto j : views::iota(0uz, i)) {
                    co_yield {view[i], view[j]};
                }
            }
        };

        for(auto [i, j] : join(hFences | views::all)) {
            ydiff.emplace(i - j);
        }
        for(auto [i, j] : join(vFences | views::all)) {
            if(ydiff.contains(i - j)) best = max(best, i - j);
        }

        if(!best) return -1;
        constexpr int mod = 1e9 + 7;
        long long ans = best;
        ans = ans * best % mod;
        return ans;
    }
};

Link

LeetCode-2975 Maximum Square Area by Removing Fences From a Field