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

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

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

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

m == grid.length。

n == grid[i].length。

1 <= m, n <= 50。

0 <= grid[i][j] < 2500。

输入: 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. 返回总操作次数：处理完所有列后，返回累计的操作次数。

具体过程（以示例为例）

• 第 0 列: [3, 1, 3, 0]
  • 初始化: [3, 1, 3, 0], res = 0
  • 处理第 1 行 (r=1): 1 <= 3 → 需要调整为 4 (操作次数: 3), 更新为 [3, 4, 3, 0], res = 3
  • 处理第 2 行 (r=2): 3 <= 4 → 需要调整为 5 (操作次数: 2), 更新为 [3, 4, 5, 0], res = 5
  • 处理第 3 行 (r=3): 0 <= 5 → 需要调整为 6 (操作次数: 6), 更新为 [3, 4, 5, 6], res = 11
• 第 1 列: [2, 3, 4, 1]
  • 初始化: [2, 3, 4, 1], res = 0
  • 处理第 1 行 (r=1): 3 > 2 → 无需操作
  • 处理第 2 行 (r=2): 4 > 3 → 无需操作
  • 处理第 3 行 (r=3): 1 <= 4 → 需要调整为 5 (操作次数: 4), 更新为 [2, 3, 4, 5], res = 4
• 总操作次数: 11 (第 0 列) + 4 (第 1 列) = 15

时间复杂度和空间复杂度

• 时间复杂度：O(m * n)，其中 m 是行数，n 是列数。因为需要遍历每一列（n 次），对于每一列需要遍历每一行（m 次）。
• 额外空间复杂度：O(1)。除了输入和输出外，只使用了常数级别的额外空间（如临时变量 res、循环变量等）。如果按原代码中的 l 数组计算，空间复杂度为 O(m)，但可以优化为 O(1) 直接修改原数组或使用临时变量。

Go完整代码如下：

package main

import (
	"fmt"
)

func minimumOperations(grid [][]int) int {
	res := 0
	rows := len(grid)
	if rows == 0 {
		return 0
	}
	cols := len(grid[0])

	// 按列处理（模拟 zip(*grid)）
	for c := 0; c < cols; c++ {
		l := make([]int, rows)
		// 先把grid这一列的元素赋值给l
		for r := 0; r < rows; r++ {
			l[r] = grid[r][c]
		}
		for j := 1; j < rows; j++ {
			if l[j] > 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:
        return 0
    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 res


if __name__ == "__main__":
    grid = [[3, 2], [1, 3], [3, 4], [0, 1]]
    result = minimum_operations(grid)
    print(result)