题目简述3989. 网格中保持一致的最大列数给定一个 m x n 的二维整数数组 grid 和一个整数 limit。你可以删除任意数量至少保留一列的列剩余列保持原有相对顺序。如果对于每一行中的任意相邻保留列 a 和 ba 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 实现javaclass 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 列是否兼容所有行的差值 ≤ limitprivate 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 数组---示例验证示例 1grid [[-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示例 2grid [[1,-1,1],[2,2,2]], limit 1· 列 0 和列 2行0差 0行1差 0 ✅· 最优保留列 0、2 → 答案 2示例 3grid [[-5,5]], limit 9· 两列差值 10 9只能保留一列 → 答案 1