海南省网站建设_网站建设公司_测试工程师_seo优化

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

题干：网格由n + 2条水平线和m + 2条竖直线组成，形成1x1 的单元格。网格中的线条从1开始编号。返回网格中正方形空洞的最大面积。

贪心地，删的线段越多，面积越大，那就先把所有能删的线段都删掉，计算最大的矩形，长宽分别是多少。取长宽的最小值，即为正方形的边长（多删的线段撤销删除）。

以 hBars 为例：

• 不删，最长长度是 1。
• 删除一条线段，最长长度是 2。
• 删除两条编号相邻的线段，最长长度是 3。
• 删除三条编号连续的线段（例如 2,3,4），最长长度是 4。
• 依此类推。

所以本题要做的是，把数组排序后，求最长连续递增子数组的长度加一。正方形的边长是长宽的最小值，其平方即为正方形的面积。

class Solution { public: int maximizeSquareHoleArea(int n, int m, vector<int>& hBars, vector<int>& vBars) { auto f=[&](vector<int>& nums){ int ans=1,cnt=1; sort(nums.begin(),nums.end()); for(int i=1;i<nums.size();i++){ if(nums[i]==nums[i-1]+1) ans=max(ans,++cnt); else cnt=1; } return ans+1; }; int x=min(f(hBars),f(vBars)); return x*x; } };