2026-10-14：网格中保持一致的最大列数。用go语言，给定一个 m 行 n 列的整数矩阵 grid，以及一个整数 limit。 你可以从矩阵中删掉若干列

2026-10-14：网格中保持一致的最大列数。用go语言，给定一个 m 行 n 列的整数矩阵 grid，以及一个整数 limit。

你可以从矩阵中删掉若干列，删多少列都可以，但最后至少要留下一列。留下的列必须保持它们在原矩阵中的先后顺序，不能打乱。

如果对于矩阵的每一行来说，在留下的列中，任意两个相邻的列，该行在这两列上的数值之差的绝对值都不超过 limit，那么这个保留方案就称为一致的。

要求：在所有一致的保留方案中，找出能够保留的最大列数。

1 <= m == grid.length <= 250。

1 <= n == grid[i].length <= 250。

-100000 <= grid[i][j] <= 100000。

0 <= limit <= 100000。

输入： grid = [[-2,0,3]], limit = 2。

输出： 2。

解释：

移除列 2 并保留列 0 和列 1，得到 |grid[0][1] − grid[0][0]| = |0 − (−2)| = 2 <= limit。

因此，最多可以保留 2 列。

题目来自力扣3989。

1. 整体思路

这是一个动态规划问题。
定义f[i]表示：以第 i 列作为最后一个保留列时，能够保留的最大列数。
最终答案就是所有f[i]中的最大值。

2. 初始化

• • 首先获取矩阵的列数n。

• • 创建一个长度为n的数组f，初始值全为 0。

• • 准备一个变量ans，用来记录全局最大保留列数，初始为 0。

从第 0 列开始，一直到第n-1列，依次把当前列i当作“最后一个保留列”来考虑。

对于每个i，初始时f[i]为 0。

4. 内层循环：枚举前一个保留列

对于当前列i，从i-1开始向前枚举，一直到第 0 列，把每个列j当作“上一个保留列”的候选。

对于每个候选列j，进行以下判断：

4.1 剪枝判断

如果f[j] <= f[i]，说明以列j结尾的最长一致列数并不比当前已经找到的以列i结尾的候选值更大。
即使列j能够和列i相邻，也不会让f[i]变得更大，因此直接跳过这个j，继续看更小的j。

4.2 一致性检查

如果f[j] > f[i]，则进一步检查列i和列j是否满足题目要求的一致性条件。

检查方式是：遍历矩阵的每一行，对于每一行，计算该行在列i和列j上的数值之差的绝对值。
如果存在任意一行，这个绝对值大于limit，说明列i和列j不能作为相邻的保留列。
此时放弃当前j，继续尝试下一个更小的j。

如果所有行都满足差值绝对值不超过limit，则说明列j可以作为列i的前一个保留列。

4.3 更新 f[i]

当列j满足条件时，说明可以在以j结尾的保留方案后面接上列i。
因此，以i结尾的保留方案可以继承以j结尾的列数，即令f[i] = f[j]。

注意：此时还没有加上列i本身，所以先暂时把f[i]赋值为f[j]。

由于内层循环是从大到小枚举j，并且只有当f[j] > f[i]时才可能更新，所以最终f[i]会记录满足条件的最大的f[j]值。

5. 加上当前列本身

内层循环结束后，无论f[i]是否被更新过，都需要将f[i]加 1。
因为以第i列作为最后一个保留列，至少要把第i列本身保留下来，所以列数要在继承的基础上加一。

即：f[i] = f[i] + 1。

6. 更新全局最大值

每处理完一个i，就用f[i]去更新全局最大值ans。
ans始终记录到目前为止所有f[i]中的最大值。

7. 返回结果

当所有列都处理完毕后，返回ans，它就是能够保留的最大列数。

8. 举例说明

以题目中的例子grid = [[-2, 0, 3]]，limit = 2为例：

• • 列数n = 3。

• • 处理第 0 列：没有前一个列，f[0]加 1 后为 1，ans = 1。

• • 处理第 1 列：枚举前一个列j = 0。f[0] = 1 > f[1] = 0，检查第 0 行：|0 - (-2)| = 2 <= 2，满足条件。于是f[1] = f[0] = 1。内层结束，f[1]加 1 变为 2，ans = 2。

• • 处理第 2 列：枚举j = 1，f[1] = 2 > f[2] = 0，检查第 0 行：|3 - 0| = 3 > 2，不满足，跳过。枚举j = 0，f[0] = 1 > f[2] = 0，检查第 0 行：|3 - (-2)| = 5 > 2，不满足，跳过。内层结束，f[2]加 1 变为 1。ans仍为 2。

• • 最终返回 2。

• • 外层循环遍历n列，内层循环对于每个i最多遍历i次，因此总的枚举次数为n(n-1)/2，即O(n^2)。

• • 在每次枚举中，最坏情况下需要检查矩阵的所有行，行数为m。

• • 因此总的时间复杂度为O(m * n^2)。

其中m是矩阵行数，n是矩阵列数。

额外空间复杂度

• • 主要额外空间是动态规划数组f，长度为n。

• • 其他变量都是常数级别。

• • 因此总的额外空间复杂度为O(n)。

总结：
该算法通过动态规划，从每一列向前寻找可以相邻保留的列，逐步构建以当前列为结尾的最大一致列数，最终得到全局最大值。时间复杂度为O(m * n^2)，额外空间复杂度为O(n)。

Go完整代码如下：

package main

 import (
    "fmt"
)

 func maxConsistentColumns(grid [][]int, limit int) (ans int) {
    n := len(grid[0])
    f := make([]int, n)
    for i := range n {
    next:
        for j := i - 1; j >= 0; j-- { // 枚举上一个保留的列
            if f[j] <= f[i] {
                continue
            }
            for _, row := range grid {
                if abs(row[i]-row[j]) > limit {
                    continue next // 列 i 和列 j 不是一致的
                }
            }
            f[i] = f[j] // +1 提到循环外面
        }
        f[i]++
        ans = max(ans, f[i])
    }
    return
}

 func abs(x int)int {
    if x < 0 {
        return -x
    }
    return x
}

 func main() {
    grid := [][]int{{-2, 0, 3}}
    limit := 2
    result := maxConsistentColumns(grid, limit)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 defmax_consistent_columns(grid, limit):
    n = len(grid[0])
    f = [0] * n
    ans = 0

     for i inrange(n):
        for j inrange(i - 1, -1, -1):
            # 如果以 j 结尾的最长一致列数不大于当前 f[i]，则跳过
            if f[j] <= f[i]:
                continue

             # 检查所有行，列 i 和列 j 是否满足差值限制
            ok = True
            for row in grid:
                ifabs(row[i] - row[j]) > limit:
                    ok = False
                    break

             if ok:
                f[i] = f[j]

         f[i] += 1
        ans = max(ans, f[i])

     return ans

 defmain():
    grid = [[-2, 0, 3]]
    limit = 2
    result = max_consistent_columns(grid, limit)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

#include  

#include  

#include  
// for std::abs
#include  
// for std::max

 usingnamespace std;

 int maxConsistentColumns(vector 
 
 int 
 >>& grid,  
 int 
  limit) 
  {
    int m = grid.size();
    int n = grid[0].size();
    vector f(n, 0);
    int ans = 0;

     for (int i = 0; i < n; ++i) {
        // 枚举上一个保留的列 j
        for (int j = i - 1; j >= 0; --j) {
            // 如果以 j 结尾的最长一致列数不大于当前 f[i]，则跳过
            if (f[j] <= f[i]) {
                continue;
            }

             // 检查所有行，列 i 和列 j 是否满足差值限制
            bool ok = true;
            for (int r = 0; r < m; ++r) {
                if (abs(grid[r][i] - grid[r][j]) > limit) {
                    ok = false;
                    break;
                }
            }

             if (ok) {
                f[i] = f[j];
            }
        }

         ++f[i];
        ans = max(ans, f[i]);
    }

     return ans;
}

 int main() {
    vector 
 
 int 
 >> grid = {{ 
 -2 
 ,  
 0 
 ,  
 3 
 }}; 
 
 
      
 int 
  limit =  
 2 
 ; 
 
 
      
 int 
  result =  
 maxConsistentColumns 
 (grid, limit); 
 
 
     cout << result << endl; 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。