DeepSeek LeetCode 3989. 网格中保持一致的最大列数 Java实现
题目简述
3989. 网格中保持一致的最大列数：给定一个 m x n 的二维整数数组 grid 和一个整数 limit。你可以删除任意数量（至少保留一列）的列，剩余列保持原有相对顺序。如果对于每一行中的任意相邻保留列 a 和 b（a < b），都有 |grid[i][b] - grid[i][a]| <= limit，则称该网格是 一致 的。返回可以保留的最大列数。
约束：m, n ≤ 250，允许 O(n²·m) 的 DP 解法。
---
核心思路：最长上升子序列 (LIS) 变种
关键转化：选择保留的列，必须满足任意两列之间（不只是相邻）在所有行上的差值都不超过 limit。但由于差值满足三角不等式，只要相邻保留列满足条件，所有列之间都满足条件。
因此问题转化为：在 n 列中，选择一个最长子序列，使得子序列中任意相邻两列 c1 < c2，对每一行 i 都有 |grid[i][c2] - grid[i][c1]| <= limit。
DP 定义：
· dp[j] = 以第 j 列结尾的最长保留列数
· 初始值 dp[j] = 1（单独保留一列）
· 转移：dp[j] = max(dp[j], dp[i] + 1)，其中 i < j 且第 i 列和第 j 列兼容（所有行的差值 ≤ limit）
答案：max(dp)，因为不要求以某一列结尾。
---
Java 实现
```java
class Solution {
public int maxConsistentColumns(int[][] grid, int limit) {
int m = grid.length;
int n = grid[0].length;
// dp[j] = 以第 j 列结尾的最长保留列数
int[] dp = new int[n];
int ans = 1;
for (int j = 0; j < n; j++) {
dp[j] = 1; // 只保留第 j 列本身
for (int i = 0; i < j; i++) {
if (canPlace(grid, i, j, limit)) {
dp[j] = Math.max(dp[j], dp[i] + 1);
}
}
ans = Math.max(ans, dp[j]);
}
return ans;
}
// 检查第 i 列和第 j 列是否兼容（所有行的差值 ≤ limit）
private boolean canPlace(int[][] grid, int i, int j, int limit) {
for (int[] row : grid) {
if (Math.abs(row[j] - row[i]) > limit) {
return false;
}
}
return true;
}
}
```
---
复杂度分析
指标 复杂度
时间复杂度 O(n²·m)，n, m ≤ 250，约 1560 万次操作，可接受
空间复杂度 O(n)，仅需一维 DP 数组
---
示例验证
示例 1：grid = [[-2,0,3]], limit = 2
· 列 0 和列 1：|0 - (-2)| = 2 ≤ 2 ✅
· 列 1 和列 2：|3 - 0| = 3 > 2 ❌
· 列 0 和列 2：|3 - (-2)| = 5 > 2 ❌
· 最优：保留列 0、1 → 答案 2
示例 2：grid = [[1,-1,1],[2,2,2]], limit = 1
· 列 0 和列 2：行0差 0，行1差 0 ✅
· 最优：保留列 0、2 → 答案 2
示例 3：grid = [[-5,5]], limit = 9
· 两列差值 10 > 9，只能保留一列 → 答案 1