最大加号标志

难度: Medium

在一个 n x n 的矩阵 grid 中，除了在数组 mines 中给出的元素为 0，其他每个元素都为 1。mines[i] = [x_i, y_i]表示 grid[x_i][y_i] == 0

返回 grid 中包含 1 的最大的 轴对齐 加号标志的阶数 。如果未找到加号标志，则返回 0 。

一个 k 阶由 1 组成的 “轴对称”加号标志 具有中心网格 grid[r][c] == 1 ，以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。注意，只有加号标志的所有网格要求为 1 ，别的网格可能为 0 也可能为 1 。

示例 1：

输入: n = 5, mines = [[4, 2]]
输出: 2
解释: 在上面的网格中，最大加号标志的阶只能是2。一个标志已在图中标出。

示例 2：

输入: n = 1, mines = [[0, 0]]
输出: 0
解释: 没有加号标志，返回 0 。

提示：

1 <= n <= 500
1 <= mines.length <= 5000
0 <= x_i, y_i < n
每一对 (x_i, y_i) 都 不重复

Submission

运行时间: 632 ms

内存: 0.0 MB

class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        if len(mines) == n * n: return 0

        xs, ys = [[-1, n] for _ in range(n)], [[-1, n] for _ in range(n)]
        for r, c in mines:
            heappush(xs[r], c)
            heappush(ys[c], r)

        res = 0
        up, down = [heappop(col) for col in ys], [heappop(col) for col in ys]
        for r in range(n):
            right = heappop(xs[r])
            while len(xs[r]) > 0:
                left, right = right, heappop(xs[r])
                for c in range(left + res + 1, right - res):
                    while down[c] <= r:
                        up[c], down[c] = down[c], heappop(ys[c])
                    res = max(res, min(c - left, right - c, r - up[c], down[c] - r))

        return res

Explain

该题解的思路是先将所有的mines位置存储在两个数组xs和ys中，xs[i]表示第i行中mines的列坐标，ys[i]表示第i列中mines的行坐标，并且都按升序排列。然后从左到右遍历每一行，对于每个可能的中心位置(r,c)，通过xs数组找到其左右两侧最近的mines位置left和right，通过ys数组找到其上下两侧最近的mines位置up[c]和down[c]，然后计算以(r,c)为中心的最大加号标志的阶数，并更新全局最大值res。

时间复杂度: O(n^2 log m)

空间复杂度: O(n)

```python
class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        if len(mines) == n * n: return 0

        # 初始化xs和ys数组，xs[i]表示第i行中mines的列坐标，ys[i]表示第i列中mines的行坐标
        xs, ys = [[-1, n] for _ in range(n)], [[-1, n] for _ in range(n)]
        for r, c in mines:
            heappush(xs[r], c)
            heappush(ys[c], r)

        res = 0
        # 初始化up和down数组，up[i]表示第i列中最靠上的mines行坐标，down[i]表示第i列中最靠下的mines行坐标
        up, down = [heappop(col) for col in ys], [heappop(col) for col in ys]
        for r in range(n):
            right = heappop(xs[r])
            while len(xs[r]) > 0:
                left, right = right, heappop(xs[r]) # left为左侧最近的mines列坐标，right为右侧最近的mines列坐标
                for c in range(left + res + 1, right - res):
                    while down[c] <= r:
                        up[c], down[c] = down[c], heappop(ys[c]) # 更新up和down数组
                    res = max(res, min(c - left, right - c, r - up[c], down[c] - r)) # 计算以(r,c)为中心的最大加号标志阶数

        return res
```

Explore

在题解中，预处理步骤涉及将所有矿的位置（mines）存储在xs和ys数组中。这里，xs和ys是列表的列表，其中xs[i]存储第i行中所有矿的列坐标，ys[i]存储第i列中所有矿的行坐标。通过遍历所有矿的位置，使用heappush函数将每个矿的列坐标加入到对应行的xs列表中，将每个矿的行坐标加入到对应列的ys列表中。此外，每个列表初始包含-1和n，这表示边界外的虚拟矿的位置，以便于后续处理。这种方法确保了xs和ys能够准确且有效地反映每行每列矿的位置，为计算最大加号标志提供了必要的信息。

在题解中，使用堆结构（具体是最小堆）进行heappush和heappop操作，是为了高效地管理和访问每行和每列中矿的位置信息。使用堆结构允许我们以对数时间复杂度O(log n)插入新元素（heappush操作），同时也能以常数时间O(1)获得最小元素（heappop操作来获取堆顶元素），这在算法中用于快速定位每个位置左右和上下的最近矿。这种数据结构的选择，特别是对于频繁的插入和获取最小元素的操作，相比其他如数组或链表结构，在性能上有显著优势，尤其是在处理较大规模数据时。这有助于提高整体算法效率，尤其是在动态更新矿位置信息时。

题解中的up和down数组分别用于存储每列中最靠上和最靠下的矿的行坐标。这两个数组的初始化是通过遍历ys数组，使用heappop操作从每个列的最小堆中弹出最小元素（即最上方的矿位置）来完成的。初始化后，up数组存储的是每列中最上方的矿的位置，而down数组存储的是对应列的下一个矿的位置。在算法执行过程中，当我们遍历到某个列的某个行时，如果当前行号大于down数组中存储的行号，我们会更新up数组为当前down的值，然后从ys的对应堆中继续pop出新的down值。这种更新机制保证了每次计算可能的加号标志大小时，我们都可以快速准确地知道每个位置的上下最近的矿的位置。这种机制足够处理所有的边界情况，因为它考虑了所有可能的矿的位置，并且动态更新以适应不同位置的查询，确保每次计算都基于最新的矿位置信息。