LeetCode 题解工作台
最大化网格图中正方形空洞的面积
给你两个整数 n 和 m ，以及两个整数数组 hBars 和 vBars 。网格由 n + 2 条水平线和 m + 2 条竖直线组成，形成 1x1 的单元格。网格中的线条从 1 开始编号。 你可以从 hBars 中 删除 一些水平线条，并从 vBars 中删除一些竖直线条。注意，其他线条是固定的，无…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·排序
答案摘要
题目实际上要我们找出数组中最长的连续递增子序列的长度，然后再加上 。 我们定义一个函数 ，表示数组 中最长的连续递增子序列的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·排序 题型思路
题目描述
给你两个整数 n 和 m，以及两个整数数组 hBars 和 vBars。网格由 n + 2 条水平线和 m + 2 条竖直线组成，形成 1x1 的单元格。网格中的线条从 1 开始编号。
你可以从 hBars 中 删除 一些水平线条，并从 vBars 中删除一些竖直线条。注意，其他线条是固定的，无法删除。
返回一个整数表示移除一些线条（可以不移除任何线条）后，网格中 正方形空洞的最大面积 。
示例 1：
输入: n = 2, m = 1, hBars = [2,3], vBars = [2]
输出: 4
解释:
左侧图片展示了网格的初始状态。水平线是 [1,2,3,4]，竖直线是 [1,2,3]。
构造最大正方形空洞的一种方法是移除水平线 2 和竖直线 2。
示例 2：
输入: n = 1, m = 1, hBars = [2], vBars = [2]
输出: 4
解释:
移除水平线 2 和竖直线 2，可以得到最大正方形空洞。
示例 3：
输入: n = 2, m = 3, hBars = [2,3], vBars = [2,4]
输出: 4
解释:
构造最大正方形空洞的一种方法是移除水平线 3 和竖直线 4。
提示：
1 <= n <= 1091 <= m <= 1091 <= hBars.length <= 1002 <= hBars[i] <= n + 11 <= vBars.length <= 1002 <= vBars[i] <= m + 1hBars中所有值互不相同。vBars中所有值互不相同。
解题思路
方法一：排序
题目实际上要我们找出数组中最长的连续递增子序列的长度，然后再加上 。
我们定义一个函数 ，表示数组 中最长的连续递增子序列的长度。
对于数组 ，我们先对其进行排序，然后遍历数组，如果当前元素 等于前一个元素 加 ，则说明当前元素可以加入到连续递增子序列中，否则，说明当前元素不能加入到连续递增子序列中，我们需要重新开始计算连续递增子序列的长度。最后，我们返回连续递增子序列的长度加 。
我们在求出 和 中最长的连续递增子序列的长度之后，我们取两者中的最小值作为正方形的边长，然后再求出正方形的面积即可。
时间复杂度 ，空间复杂度 。其中 为数组 或 的长度。
class Solution:
def maximizeSquareHoleArea(
self, n: int, m: int, hBars: List[int], vBars: List[int]
) -> int:
def f(nums: List[int]) -> int:
nums.sort()
ans = cnt = 1
for i in range(1, len(nums)):
if nums[i] == nums[i - 1] + 1:
cnt += 1
ans = max(ans, cnt)
else:
cnt = 1
return ans + 1
return min(f(hBars), f(vBars)) ** 2
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(hBars.length log hBars.length + vBars.length log vBars.length) due to sorting. Space complexity is O(1) additional beyond the input arrays, as only gap calculations are needed. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Sorting arrays is expected before evaluating gaps.
- question_mark
Focus on consecutive distances between bars rather than all combinations.
- question_mark
Clarify edge cases where the largest square is at the grid boundary.
常见陷阱
外企场景- error
Forgetting to include the gaps at the edges of the grid outside the removable bars.
- error
Assuming removing all bars always gives the largest square instead of computing actual gaps.
- error
Ignoring the distinct nature of hBars and vBars and indexing from 1.
进阶变体
外企场景- arrow_right_alt
Compute largest rectangular hole instead of square-shaped hole using similar gap calculations.
- arrow_right_alt
Handle cases where some bars cannot be removed by marking them as fixed obstacles in the array.
- arrow_right_alt
Maximize square area with weighted bars where removing each bar has a cost.