DeepSeek LeetCode 3989. 网格中保持一致的最大列数 Python3实现

题目简述

3989. 网格中保持一致的最大列数：给定 m x n 网格 grid 和整数 limit，删除若干列后（至少保留一列），若每一行中任意相邻保留列的绝对值差都不超过 limit，则称该网格为一致的。求能保留的最大列数。

约束：m, n ≤ 250，允许 O(n²·m) 的动态规划。

---

核心思路：最长兼容子序列（LIS 变种）

· 兼容性：第 i 列与第 j 列（i < j）可相邻保留，当且仅当所有行上 |grid[row][j] - grid[row][i]| ≤ limit。
· DP 定义：dp[j] 表示以第 j 列结尾的最长保留列数。
· 转移：dp[j] = max(dp[j], dp[i] + 1)，其中 i < j 且 i 与 j 兼容。
· 答案：max(dp)。

---

Python3 实现

```python
from typing import List

class Solution:
def maxConsistentColumns(self, grid: List[List[int]], limit: int) -> int:
m = len(grid)
n = len(grid[0])

# dp[j] = 以第 j 列结尾的最长保留列数
dp = [1] * n
ans = 1

for j in range(n):
for i in range(j):
# 检查列 i 和列 j 是否兼容
compatible = True
for row in range(m):
if abs(grid[row][j] - grid[row][i]) > limit:
compatible = False
break
if compatible:
dp[j] = max(dp[j], dp[i] + 1)
ans = max(ans, dp[j])

return ans
```

---

复杂度分析

指标 复杂度
时间复杂度 O(n²·m)，最坏约 250² × 250 = 1562.5 万次比较，Python 可轻松通过
空间复杂度 O(n)，仅一维 DP 数组

---

示例验证

示例 1
grid = [[-2,0,3]], limit = 2

· 列 0 与 1 兼容（差 2），列 1 与 2 不兼容（差 3），列 0 与 2 不兼容（差 5）
· 最优保留 [0,1] → 答案 2

示例 2
grid = [[1,-1,1],[2,2,2]], limit = 1

· 列 0 与 2 兼容（两行差均为 0）
· 最优保留 [0,2] → 答案 2

示例 3
grid = [[-5,5]], limit = 9

· 两列差值 10 > 9，不能同时保留，只能保留一列 → 答案 1