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 行没有前一行需要比较），检查当前行的值是否大于前一行的值。

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

o 如果当前值 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. 返回总操作次数：处理完所有列后，返回累计的操作次数。

具体过程（以示例为例）

o 第 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

o 第 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

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

时间复杂度和空间复杂度

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

o 额外空间复杂度：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 {
        return0
    }
    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:
        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 res


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

·

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

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

·