Leetcode每日一题：移除栅栏得到的正方形田地的最大面积

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

思路：
今天的思路与昨天差异很大。昨天的题是每个坐标都有栅栏，部分可移除，今天的题是不是所有坐标都有栅栏，这就导致允许的宽度是离散的而不是连续的。
整体思路大同小异，求取所有可能得水平、垂直宽度，然后取双向都存在的最大的宽度相乘即可。

代码：

    public int maximizeSquareArea(int m, int n, int hFences, int vFences) {
        // 存放水平方向可能的宽度
        HashSet<Integer> set = new HashSet<>();

        Arrays.sort(hFences);
        // 初始化从0到各个栅栏的宽度(包括外围栅栏)，这样可以通过栅栏位置相减直接求得任意两栅栏之间的宽度
        int hAll = new int[hFences.length + 2];
        hAll[0] = 1;
        hAll[hFences.length + 1] = m;
        System.arraycopy(hFences, 0, hAll, 1, hFences.length);

        // 计算任意两栅栏之间的宽度，存入set中
        for (int i = 0; i <= hFences.length; i++) {
            for (int j = i + 1; j < hAll.length; j++) {
                int w = hAll[j] - hAll[j - i - 1];
                set.add(w);
            }
        }

        // 当前最大可用宽度
        int max = 0;
        Arrays.sort(vFences);
        // 跟水平方向一样，初始化从0到各个栅栏的宽度(包括外围栅栏)
        int vAll = new int[vFences.length + 2];
        vAll[0] = 1;
        vAll[vFences.length + 1] = n;
        System.arraycopy(vFences, 0, vAll, 1, vFences.length);

        // 计算任意两栅栏之间的宽度，如果宽度超过之前最大宽度且set中存在，则更新最大宽度
        for (int i = 0; i <= vFences.length; i++) {
            for (int j = i + 1; j < vAll.length; j++) {
                int w = vAll[j] - vAll[j - i - 1];
                if (w > max && set.contains(w)) {
                    max = w;
                }
            }
        }
        return (int) (max == 0 ? -1 : (long) max * max % 1000000007);
    }

PS：久违的耗时100%！ 🫣

3 posts - 3

：点击查看 (author: 魔法师)