mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-01-27 02:30:28 +08:00
90 lines
4.0 KiB
HTML
90 lines
4.0 KiB
HTML
|
<p>给你一个网格图，由 <code>n + 2</code> 条 <strong>横线段</strong> 和 <code>m + 2</code> 条 <strong>竖线段</strong> 组成，一开始所有区域均为 <code>1 x 1</code> 的单元格。</p>
|
|||
|
|
|
|||
|
|
<p>所有线段的编号从 <strong>1</strong> 开始。</p>
|
|||
|
|
|
|||
|
|
<p>给你两个整数 <code>n</code> 和 <code>m</code> 。</p>
|
|||
|
|
|
|||
|
|
<p>同时给你两个整数数组 <code>hBars</code> 和 <code>vBars</code> 。</p>
|
|||
|
|
|
|||
|
|
<ul>
|
|||
|
|
<li><code>hBars</code> 包含区间 <code>[2, n + 1]</code> 内 <strong>互不相同</strong> 的横线段编号。</li>
|
|||
|
|
<li><code>vBars</code> 包含 <code>[2, m + 1]</code> 内 <strong>互不相同的</strong> 竖线段编号。</li>
|
|||
|
|
</ul>
|
|||
|
|
|
|||
|
|
<p>如果满足以下条件之一，你可以 <strong>移除</strong> 两个数组中的部分线段：</p>
|
|||
|
|
|
|||
|
|
<ul>
|
|||
|
|
<li>如果移除的是横线段，它必须是 <code>hBars</code> 中的值。</li>
|
|||
|
|
<li>如果移除的是竖线段，它必须是 <code>vBars</code> 中的值。</li>
|
|||
|
|
</ul>
|
|||
|
|
|
|||
|
|
<p>请你返回移除一些线段后（<strong>可能不移除任何线段）</strong>，剩余网格图中 <strong>最大正方形</strong> 空洞的面积，正方形空洞的意思是正方形 <strong>内部</strong> 不含有任何线段。</p>
|
|||
|
|
|
|||
|
|
<p> </p>
|
|||
|
|
|
|||
|
|
<p><strong class="example">示例 1：</strong></p>
|
|||
|
|
|
|||
|
|
<p><img alt="" src="https://assets.leetcode.com/uploads/2023/11/05/screenshot-from-2023-11-05-22-40-25.png" style="width: 411px; height: 220px;" /></p>
|
|||
|
|
|
|||
|
|
<pre>
|
|||
|
|
<b>输入：</b>n = 2, m = 1, hBars = [2,3], vBars = [2]
|
|||
|
|
<b>输出：</b>4
|
|||
|
|
<b>解释：</b>左边的图是一开始的网格图。
|
|||
|
|
横线编号的范围是区间 [1,4] ，竖线编号的范围是区间 [1,3] 。
|
|||
|
|
可以移除的横线段为 [2,3] ，竖线段为 [2] 。
|
|||
|
|
一种得到最大正方形面积的方法是移除横线段 2 和竖线段 2 。
|
|||
|
|
操作后得到的网格图如右图所示。
|
|||
|
|
正方形空洞面积为 4。
|
|||
|
|
无法得到面积大于 4 的正方形空洞。
|
|||
|
|
所以答案为 4 。
|
|||
|
|
</pre>
|
|||
|
|
|
|||
|
|
<p><strong class="example">示例 2：</strong></p>
|
|||
|
|
|
|||
|
|
<p><img alt="" src="https://assets.leetcode.com/uploads/2023/11/04/screenshot-from-2023-11-04-17-01-02.png" style="width: 368px; height: 145px;" /></p>
|
|||
|
|
|
|||
|
|
<pre>
|
|||
|
|
<b>输入：</b>n = 1, m = 1, hBars = [2], vBars = [2]
|
|||
|
|
<b>输出：</b>4
|
|||
|
|
<b>解释：</b>左边的图是一开始的网格图。
|
|||
|
|
横线编号的范围是区间 [1,3] ，竖线编号的范围是区间 [1,3] 。
|
|||
|
|
可以移除的横线段为 [2] ，竖线段为 [2] 。
|
|||
|
|
一种得到最大正方形面积的方法是移除横线段 2 和竖线段 2 。
|
|||
|
|
操作后得到的网格图如右图所示。
|
|||
|
|
正方形空洞面积为 4。
|
|||
|
|
无法得到面积大于 4 的正方形空洞。
|
|||
|
|
所以答案为 4 。
|
|||
|
|
</pre>
|
|||
|
|
|
|||
|
|
<p><strong class="example">示例 3：</strong></p>
|
|||
|
|
|
|||
|
|
<p><img alt="" src="https://assets.leetcode.com/uploads/2023/11/05/screenshot-from-2023-11-05-22-33-35.png" style="width: 648px; height: 218px;" /></p>
|
|||
|
|
|
|||
|
|
<pre>
|
|||
|
|
<b>输入：</b>n = 2, m = 3, hBars = [2,3], vBars = [2,3,4]
|
|||
|
|
<b>输出：</b>9
|
|||
|
|
<b>解释：</b>左边的图是一开始的网格图。
|
|||
|
|
横线编号的范围是区间 [1,4] ，竖线编号的范围是区间 [1,5] 。
|
|||
|
|
可以移除的横线段为 [2,3] ，竖线段为 [2,3,4] 。
|
|||
|
|
一种得到最大正方形面积的方法是移除横线段 2、3 和竖线段 3、4 。
|
|||
|
|
操作后得到的网格图如右图所示。
|
|||
|
|
正方形空洞面积为 9。
|
|||
|
|
无法得到面积大于 9 的正方形空洞。
|
|||
|
|
所以答案为 9 。
|
|||
|
|
</pre>
|
|||
|
|
|
|||
|
|
<p> </p>
|
|||
|
|
|
|||
|
|
<p><strong>提示：</strong></p>
|
|||
|
|
|
|||
|
|
<ul>
|
|||
|
|
<li><code>1 <= n <= 10<sup>9</sup></code></li>
|
|||
|
|
<li><code>1 <= m <= 10<sup>9</sup></code></li>
|
|||
|
|
<li><code>1 <= hBars.length <= 100</code></li>
|
|||
|
|
<li><code>2 <= hBars[i] <= n + 1</code></li>
|
|||
|
|
<li><code>1 <= vBars.length <= 100</code></li>
|
|||
|
|
<li><code>2 <= vBars[i] <= m + 1</code></li>
|
|||
|
|
<li><code>hBars</code> 中的值互不相同。</li>
|
|||
|
|
<li><code>vBars</code> 中的值互不相同。</li>
|
|||
|
|
</ul>
|