Problem: 100138. 最大化网格图中正方形空洞的面积

[TOC]

思路

分析题意：

• 抽掉一根线，则空出空间： 2

• 若存在连续 l 根线，抽出后，空出空间为： l + 1

• hBars.length、vBars.length 至少为1，即必有线被抽掉，至少有空间 2

因此，贪心思路来考虑：

• 第一步、对 hBars 和 vBars 排序

• 第二步、分别求出 hBars 和 vBars 的连续最长线段

• 第三步、取 hBars 和 vBars 的连续最长线段两者的较小值，平方后返回

此题，n、m 两个参数可以不用到。

Code

执行用时分布0ms击败100.00%；消耗内存分布6.47MB击败100.00%

###C

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}
int maxlen(int* lst, int len) {
    qsort(lst, len, sizeof(int), cmp);
    int ma = 2, l = 2;
    for (int i = 0; i < len - 1; ++ i)
        if (lst[i + 1] - lst[i] == 1) { if (++ l > ma) ma = l; }
        else l = 2;
    return ma;
}
int maximizeSquareHoleArea(int n, int m, int* hBars, int hBarsSize, int* vBars, int vBarsSize) {
    int h = maxlen(hBars, hBarsSize), v = maxlen(vBars, vBarsSize);
    return h < v ? h * h : v * v;
}

###Python3

class Solution:
    def maximizeSquareHoleArea(self, n: int, m: int, hBars: List[int], vBars: List[int]) -> int:
        def maxlen(lst):
            ma, l = 2, 2
            for x, y in pairwise(sorted(lst)):
                if y - x == 1: 
                    l += 1
                    ma = max(ma, l)
                else:
                    l = 2
            return ma
        return min(maxlen(hBars), maxlen(vBars)) ** 2

您若还有不同方法，欢迎贴在评论区，一起交流探讨！ ^_^

↓ 点个赞，点收藏，留个言，再划走，感谢您支持作者！ ^_^