LeetCode 题解工作台
矩阵中严格递增的单元格数
给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat ，你可以选择任一单元格作为 起始单元格 。 从起始单元格出发，你可以移动到 同一行或同一列 中的任何其他单元格，但前提是目标单元格的值 严格大于 当前单元格的值。 你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行…
8
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
根据题目描述，我们顺序移动的单元格的值必须严格递增，因此，我们不妨用一个哈希表 来记录每个值对应的所有单元格的位置，然后按照值的大小从小到大遍历。 在这个过程中，我们可以维护两个数组 `rowMax` 和 `colMax`，分别记录每一行和每一列的最大递增长度。初始时，这两个数组的所有元素都为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 1 开始、大小为 m x n 的整数矩阵 mat，你可以选择任一单元格作为 起始单元格 。
从起始单元格出发，你可以移动到 同一行或同一列 中的任何其他单元格，但前提是目标单元格的值 严格大于 当前单元格的值。
你可以多次重复这一过程，从一个单元格移动到另一个单元格，直到无法再进行任何移动。
请你找出从某个单元开始访问矩阵所能访问的 单元格的最大数量 。
返回一个表示可访问单元格最大数量的整数。
示例 1：
输入：mat = [[3,1],[3,4]] 输出：2 解释：上图展示了从第 1 行、第 2 列的单元格开始，可以访问 2 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 2 个单元格，因此答案是 2 。
示例 2：
输入：mat = [[1,1],[1,1]] 输出：1 解释：由于目标单元格必须严格大于当前单元格，在本示例中只能访问 1 个单元格。
示例 3：
输入：mat = [[3,1,6],[-9,5,7]] 输出：4 解释：上图展示了从第 2 行、第 1 列的单元格开始，可以访问 4 个单元格。可以证明，无论从哪个单元格开始，最多只能访问 4 个单元格，因此答案是 4 。
提示：
m == mat.lengthn == mat[i].length1 <= m, n <= 1051 <= m * n <= 105-105 <= mat[i][j] <= 105
解题思路
方法一：排序 + 动态规划
根据题目描述，我们顺序移动的单元格的值必须严格递增，因此，我们不妨用一个哈希表 来记录每个值对应的所有单元格的位置，然后按照值的大小从小到大遍历。
在这个过程中，我们可以维护两个数组 rowMax 和 colMax，分别记录每一行和每一列的最大递增长度。初始时，这两个数组的所有元素都为 。
对于每个值对应的所有单元格位置，我们按照位置顺序遍历，对于每个位置 ，我们可以计算出以该位置为终点的最大递增长度为 ，更新答案，然后更新 rowMax[i] 和 colMax[j]。
最后返回答案即可。
时间复杂度 ，空间复杂度 。
class Solution:
def maxIncreasingCells(self, mat: List[List[int]]) -> int:
m, n = len(mat), len(mat[0])
g = defaultdict(list)
for i in range(m):
for j in range(n):
g[mat[i][j]].append((i, j))
rowMax = [0] * m
colMax = [0] * n
ans = 0
for _, pos in sorted(g.items()):
mx = []
for i, j in pos:
mx.append(1 + max(rowMax[i], colMax[j]))
ans = max(ans, mx[-1])
for k, (i, j) in enumerate(pos):
rowMax[i] = max(rowMax[i], mx[k])
colMax[j] = max(colMax[j], mx[k])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Understanding the importance of bottom-up dynamic programming for efficiently computing path lengths.
- question_mark
Demonstrating familiarity with hash table optimizations for matrix traversal.
- question_mark
Being able to handle large inputs by applying efficient traversal techniques such as binary search.
常见陷阱
外企场景- error
Not leveraging dynamic programming effectively, resulting in redundant calculations.
- error
Failing to implement hash lookups or forgetting to store already computed paths.
- error
Not optimizing for large input sizes, leading to time limit exceeded errors.
进阶变体
外企场景- arrow_right_alt
Consider variations where you are limited to only vertical or horizontal moves.
- arrow_right_alt
Explore the case where you need to find the longest path from a specified starting point.
- arrow_right_alt
Handle matrices where values are guaranteed to be sorted, requiring additional optimizations.