學習路線/幾何

2943. 網格中最大正方形孔洞的面積

Medium

Maximize Area of Square Hole in Grid

ArrayGreedySorting

題目描述

給定一個 n×m 的網格，可以移除某些水平和垂直的內部柵欄。給定可移除的柵欄列表，求移除後能形成的最大正方形孔洞的面積。

LeetCode 2943原題連結 →

解法思路

  1. 分別對水平和垂直可移除柵欄排序
  2. 找出各方向上最長的連續可移除柵欄段（連續柵欄可合併成更大的間隙）
  3. 最大正方形邊長 = min(最長水平連續段 + 1, 最長垂直連續段 + 1)
  4. 返回邊長的平方作為面積

複雜度分析

  • 時間複雜度：O(h log h + v log v)
  • 空間複雜度：O(1)

最大正方形面積

1

1 × 1

可移除的水平柵欄（點擊切換）
可移除的垂直柵欄（點擊切換）

點擊藍色/紫色的柵欄來移除或恢復它們，觀察最大正方形孔洞面積的變化。