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 实现pythonfrom typing import Listclass Solution:def maxConsistentColumns(self, grid: List[List[int]], limit: int) - int:m len(grid)n len(grid[0])# dp[j] 以第 j 列结尾的最长保留列数dp [1] * nans 1for j in range(n):for i in range(j):# 检查列 i 和列 j 是否兼容compatible Truefor row in range(m):if abs(grid[row][j] - grid[row][i]) limit:compatible Falsebreakif 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 数组---示例验证示例 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