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

题目简述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] Math.max(dp[j], dp[i] 1)其中 i j 且 i 与 j 兼容。· 答案Math.max(...dp)。---TypeScript 实现typescriptfunction maxConsistentColumns(grid: number[][], limit: number): number {const m grid.length;const n grid[0].length;// dp[j] 以第 j 列结尾的最长保留列数const dp: number[] new Array(n).fill(1);let ans 1;for (let j 0; j n; j) {for (let i 0; i j; i) {// 检查列 i 和列 j 是否兼容let compatible true;for (let row 0; row m; row) {if (Math.abs(grid[row][j] - grid[row][i]) limit) {compatible false;break;}}if (compatible) {dp[j] Math.max(dp[j], dp[i] 1);}}ans Math.max(ans, dp[j]);}return ans;}---复杂度分析指标 复杂度时间复杂度 O(n²·m)最坏约 250² × 250 ≈ 1560 万次比较可接受空间复杂度 O(n)仅一维 DP 数组---示例验证示例 1grid [[-2,0,3]], limit 2· 列 0 与 1 兼容差 2列 1 与 2 不兼容差 3列 0 与 2 不兼容差 5· 最优保留 [0,1] → 答案 2示例 2grid [[1,-1,1],[2,2,2]], limit 1· 列 0 与 2 兼容两行差均为 0· 最优保留 [0,2] → 答案 2示例 3grid [[-5,5]], limit 9· 两列差值 10 9不能同时保留只能保留一列 → 答案 1