Easy

题目描述

给你一个 m x n 的矩阵 grid，由非负整数组成。

在一次操作中，你可以将任意 grid[i][j] 的值增加 1。

返回使 grid 的所有列都严格递增所需的最少操作次数。

示例 1：

输入：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 次操作。

示例 2：

输入：grid = [[3,2,1],[2,1,0],[1,2,3]]
输出：12
解释：
- 要使第 0 列严格递增，我们可以对 grid[1][0] 进行 2 次操作，对 grid[2][0] 进行 4 次操作。
- 要使第 1 列严格递增，我们可以对 grid[1][1] 进行 2 次操作，对 grid[2][1] 进行 2 次操作。
- 要使第 2 列严格递增，我们可以对 grid[1][2] 进行 2 次操作。

约束：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 0 <= grid[i][j] < 2500

解题思路

这是一道经典的贪心算法题。要使每一列都严格递增，我们需要确保对于任意相邻的两行 i 和 i+1，都满足 grid[i+1][j] > grid[i][j]。

核心思路：

  1. 对于每一列，从上到下逐行处理
  2. 如果当前行的元素小于等于上一行的元素，需要将其增加到 上一行元素 + 1
  3. 统计所有需要的操作次数

算法步骤：

  • 遍历每一列
  • 对于每一列，从第二行开始向下检查
  • 如果 grid[i][j] <= grid[i-1][j]，则需要进行 grid[i-1][j] + 1 - grid[i][j] 次操作
  • 更新 grid[i][j] 为 grid[i-1][j] + 1，并累加操作次数

这种贪心策略是最优的，因为我们总是选择使当前元素刚好满足严格递增条件的最小值，这样不会影响后续元素的最优选择。

时间复杂度为 O(m×n)，空间复杂度为 O(1)（原地修改）。

代码实现

class Solution {
public:
    int minimumOperations(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        int operations = 0;
        
        for (int j = 0; j < n; j++) {
            for (int i = 1; i < m; i++) {
                if (grid[i][j] <= grid[i-1][j]) {
                    int needed = grid[i-1][j] + 1 - grid[i][j];
                    operations += needed;
                    grid[i][j] = grid[i-1][j] + 1;
                }
            }
        }
        
        return operations;
    }
};

class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        operations = 0
        
        for j in range(n):
            for i in range(1, m):
                if grid[i][j] <= grid[i-1][j]:
                    needed = grid[i-1][j] + 1 - grid[i][j]
                    operations += needed
                    grid[i][j] = grid[i-1][j] + 1
        
        return operations

public class Solution {
    public int MinimumOperations(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        int operations = 0;
        
        for (int j = 0; j < n; j++) {
            for (int i = 1; i < m; i++) {
                if (grid[i][j] <= grid[i-1][j]) {
                    int needed = grid[i-1][j] + 1 - grid[i][j];
                    operations += needed;
                    grid[i][j] = grid[i-1][j] + 1;
                }
            }
        }
        
        return operations;
    }
}

var minimumOperations = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    let operations = 0;
    
    for (let j = 0; j < n; j++) {
        for (let i = 1; i < m; i++) {
            if (grid[i][j] <= grid[i-1][j]) {
                const needed = grid[i-1][j] + 1 - grid[i][j];
                operations += needed;
                grid[i][j] = grid[i-1][j] + 1;
            }
        }
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(m × n)，其中 m 是行数，n 是列数，需要遍历每个元素一次
空间复杂度O(1)，只使用常数额外空间，原地修改矩阵

相关题目