Uber OA 面试真题解析：Largest Perfect X-Shaped Figure（最大完美 X 形）

You are given a matrix of integers matrix containing only zeros and ones.

Let’s call an x-shape a figure with a center at some cell of matrix and 4 diagonal rays of equal length. The x-shape is called perfect if all its elements equal 1.

For example, there is one perfect x-shaped figure of size 2 with a center at [1, 1], and five perfect x-shaped figures of size 1 in the following matrix:

[[1, 0, 1],
 [0, 1, 0],
 [1, 0, 1]]

At the same time, the following matrix has only four perfect x-shaped figures of size 1:

[[1, 1],
 [1, 1]]

Return the center coordinates [row, col] of the largest perfect x-shaped figure within the matrix. If there are multiple answers, return the one with the smallest row value first, and if still tied, the smallest column value.

这道题要求在只包含 0/1 的矩阵中，找到“完美 X 形”的最大中心点。关键思路是预处理每个位置向四个对角方向连续 1 的长度，然后对每个格子取四个方向的最小值，就能得到以该格为中心的最大 X 形半径；遍历所有位置并按题目要求在同半径时优先选择行更小、再选列更小的中心即可。这个题本质上是二维动态规划 / 方向 DP，时间复杂度可以做到 O(nm)，非常适合 OA 中的矩阵扫描问题。