2025-07-11：使每一列严格递增的最少操作次数。用go语言，给定一个由非负整数组成的 m 行 n 列的矩阵 grid。

每次操作中，可以选择任意一个元素 grid[i][j]，将其数值增加 1。

要求通过若干次操作，使得矩阵中每一列的元素从上到下严格递增。

请计算达到这一目标所需的最少操作次数。

m == grid.length。

n == grid[i].length。

1

0

输入: grid = [[3,2],[1,3],[3,4],[0,1]]。

输出: 15。

解释:

为了让第 0 列严格递增，可以对 grid[1][0] 执行 3 次操作，对 grid[2][0] 执行 2 次操作，对 grid[3][0] 执行 6 次操作。

为了让第 1 列严格递增，可以对 grid[3][1] 执行 4 次操作。

在这里插入图片描述

题目来自力扣3402。

解决步骤

1. 按列处理：对于每一列，我们需要确保从上到下严格递增。因此，可以逐列处理，每一列的处理是独立的。

2. 遍历每一列：对于每一列 c，从第 1 行开始（因为第 0 行没有前一行需要比较），检查当前行的值是否大于前一行的值。

• 如果当前值 grid[r][c] 大于前一行 grid[r-1][c]，则满足严格递增，无需操作。

• 如果当前值 grid[r][c] 小于或等于前一行 grid[r-1][c]，则需要将当前值增加到 grid[r-1][c] + 1。此时的操作次数为 (grid[r-1][c] + 1 - grid[r][c])，并将 grid[r][c] 更新为 grid[r-1][c] + 1。

3. 累加操作次数：对于每一列的每一次调整，将操作次数累加到总操作次数中。

4. 返回总操作次数：处理完所有列后，返回累计的操作次数。

具体过程（以示例为例）

初始化: [3, 1, 3, 0], res = 0

处理第 1 行 (r=1): 1

处理第 2 行 (r=2): 3

处理第 3 行 (r=3): 0

初始化: [2, 3, 4, 1], res = 0

处理第 1 行 (r=1): 3 > 2 → 无需操作

处理第 2 行 (r=2): 4 > 3 → 无需操作

处理第 3 行 (r=3): 1

• 总操作次数: 11 (第 0 列) + 4 (第 1 列) = 15

时间复杂度和空间复杂度

• 时间复杂度：O(m * n)，其中 m 是行数，n 是列数。因为需要遍历每一列（n 次），对于每一列需要遍历每一行（m 次）。

• 额外空间复杂度：O(1)。除了输入和输出外，只使用了常数级别的额外空间（如临时变量 res、循环变量等）。如果按原代码中的 l 数组计算，空间复杂度为 O(m)，但可以优化为 O(1) 直接修改原数组或使用临时变量。

Go完整代码如下：

.

package mainimport ( "fmt")func minimumOperations(grid [][]int)int { res := 0 rows := len(grid) if rows == 0 { return0 } cols := len(grid[0]) // 按列处理（模拟 zip(*grid)） for c := 0; c l[j-1] { continue } else { // 修改l[j] diff := (l[j-1] + 1) - l[j] res += diff l[j] = l[j-1] + 1 } } } return res}func main { grid := [][]int{{3, 2}, {1, 3}, {3, 4}, {0, 1}} result := minimumOperations(grid) fmt.Println(result)}

Python完整代码如下：

.

# -*-coding:utf-8-*-def minimum_operations(grid): res = 0 rows = len(grid) if rows == 0: return0 cols = len(grid[0]) for c in range(cols): l = [grid[r][c] for r in range(rows)] for j in range(1, rows): if l[j] > l[j - 1]: continue else: diff = (l[j - 1] + 1) - l[j] res += diff l[j] = l[j - 1] + 1 return resif __name__ == "__main__": grid = [[3, 2], [1, 3], [3, 4], [0, 1]] result = minimum_operations(grid) print(result)

·

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展