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

[TOC]

解题方法

其实这个题没有看上去那么难

只需要排序之后取两个数组差值为1的最大个数即可

计算差值为一的元素个数是因为需要统计最大能切割出多大的正方形

（周赛wa三次真的要吐血了X_X）

复杂度

时间复杂度: $O(nlogn + mlogm)$ 主要取决于排序

Code

###Java

class Solution {
    public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {
        int h = 1;
        int v = 1;
        Arrays.sort(hBars);
        Arrays.sort(vBars);
        int ht = 1;
        int vt = 1;
        for(int i = 1;i < hBars.length;i++){
            if(hBars[i] - hBars[i - 1] == 1) ht++;
            if(hBars[i] - hBars[i - 1] != 1){
                ht = 1;
            }
            h = Math.max(ht,h);
        }
        for(int i = 1;i < vBars.length;i++){
            if(vBars[i] - vBars[i - 1] == 1) vt++;
            if(vBars[i] - vBars[i - 1] != 1){
                vt = 1;
            }
            v = Math.max(vt,v);
        }
        int l = Math.min(v + 1,h + 1);
        return l * l;
    }
}