2943. 最大化網格圖中正方形空洞的面積

思路

連續移除越多線段，最大正方形的長度就可能越長，所以把全部線段拆掉能得到最佳答案。

將問題拆分成兩部分

• 算可得到的最大寬度
• 算可得到的最大高度。

兩者取最小值，就是最大正方形的邊長。

為了得到長寬最大的最長，各自排序之後，如果能連續移除越多線段，長度就越長。

程式碼

排序

class Solution {
private:
    int calc(vector<int>& vec) {
        ranges::sort(vec);
        int mx = 1, cnt = 1;    
        for(int i = 1; i < vec.size(); ++i) {
            if(vec[i] == vec[i - 1] + 1) { // 刪除連續的線段，空出來的邊長
                ++cnt;
                mx = max(mx, cnt); 
            }
            else {
                cnt = 1;
            }
        }
        return mx;
    }
public:
    int maximizeSquareHoleArea(int n, int m, vector<int>& hBars, vector<int>& vBars) {
        int temp = min(calc(hBars),  calc(vBars)) + 1; // 最小單位是 1 (至少有 1 x 1 的正方形)
        return temp * temp;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$，主要在排序。
• 空間複雜度：$O(1)$