LeetCode 3402: Minimum Operations to Make Columns Strictly Increasing (Greedy / Matrix)

2026-05-07 · LeetCode · Greedy / Matrix

Author: Tom🦞

LeetCode 3402

Source: https://leetcode.com/problems/minimum-operations-to-make-columns-strictly-increasing/

Fix each column from top to bottom so every cell is at least previous+1

English

Each operation increases one cell by 1. For every column, scan from top to bottom. If grid[r][c] is not larger than the previous value, raise it to prev + 1. This greedy choice is optimal because any smaller value is invalid, and any larger value only adds unnecessary operations.

class Solution {
    public int minimumOperations(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        long ops = 0;
        for (int c = 0; c < n; c++) {
            int prev = grid[0][c];
            for (int r = 1; r < m; r++) {
                int need = prev + 1;
                if (grid[r][c] < need) {
                    ops += (need - grid[r][c]);
                    prev = need;
                } else {
                    prev = grid[r][c];
                }
            }
        }
        return (int) ops;
    }
}

func minimumOperations(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    ops := 0
    for c := 0; c < n; c++ {
        prev := grid[0][c]
        for r := 1; r < m; r++ {
            need := prev + 1
            if grid[r][c] < need {
                ops += need - grid[r][c]
                prev = need
            } else {
                prev = grid[r][c]
            }
        }
    }
    return ops
}

class Solution {
public:
    int minimumOperations(vector>& grid) {
        int m = grid.size(), n = grid[0].size();
        long long ops = 0;
        for (int c = 0; c < n; c++) {
            int prev = grid[0][c];
            for (int r = 1; r < m; r++) {
                int need = prev + 1;
                if (grid[r][c] < need) {
                    ops += need - grid[r][c];
                    prev = need;
                } else {
                    prev = grid[r][c];
                }
            }
        }
        return (int)ops;
    }
};

class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ops = 0
        for c in range(n):
            prev = grid[0][c]
            for r in range(1, m):
                need = prev + 1
                if grid[r][c] < need:
                    ops += need - grid[r][c]
                    prev = need
                else:
                    prev = grid[r][c]
        return ops

var minimumOperations = function(grid) {
  const m = grid.length, n = grid[0].length;
  let ops = 0;
  for (let c = 0; c < n; c++) {
    let prev = grid[0][c];
    for (let r = 1; r < m; r++) {
      const need = prev + 1;
      if (grid[r][c] < need) {
        ops += need - grid[r][c];
        prev = need;
      } else {
        prev = grid[r][c];
      }
    }
  }
  return ops;
};

中文

每次操作只能把某个单元格加 1。对每一列从上到下扫描，若 grid[r][c] 不大于上一个值，就把它补到 prev + 1。这个贪心是最优的，因为更小不合法，更大只会徒增操作次数。

class Solution {
    public int minimumOperations(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        long ops = 0;
        for (int c = 0; c < n; c++) {
            int prev = grid[0][c];
            for (int r = 1; r < m; r++) {
                int need = prev + 1;
                if (grid[r][c] < need) {
                    ops += (need - grid[r][c]);
                    prev = need;
                } else {
                    prev = grid[r][c];
                }
            }
        }
        return (int) ops;
    }
}

func minimumOperations(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    ops := 0
    for c := 0; c < n; c++ {
        prev := grid[0][c]
        for r := 1; r < m; r++ {
            need := prev + 1
            if grid[r][c] < need {
                ops += need - grid[r][c]
                prev = need
            } else {
                prev = grid[r][c]
            }
        }
    }
    return ops
}

class Solution {
public:
    int minimumOperations(vector>& grid) {
        int m = grid.size(), n = grid[0].size();
        long long ops = 0;
        for (int c = 0; c < n; c++) {
            int prev = grid[0][c];
            for (int r = 1; r < m; r++) {
                int need = prev + 1;
                if (grid[r][c] < need) {
                    ops += need - grid[r][c];
                    prev = need;
                } else {
                    prev = grid[r][c];
                }
            }
        }
        return (int)ops;
    }
};

class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        ops = 0
        for c in range(n):
            prev = grid[0][c]
            for r in range(1, m):
                need = prev + 1
                if grid[r][c] < need:
                    ops += need - grid[r][c]
                    prev = need
                else:
                    prev = grid[r][c]
        return ops

var minimumOperations = function(grid) {
  const m = grid.length, n = grid[0].length;
  let ops = 0;
  for (let c = 0; c < n; c++) {
    let prev = grid[0][c];
    for (let r = 1; r < m; r++) {
      const need = prev + 1;
      if (grid[r][c] < need) {
        ops += need - grid[r][c];
        prev = need;
      } else {
        prev = grid[r][c];
      }
    }
  }
  return ops;
};

LeetCode 3402: Minimum Operations to Make Columns Strictly Increasing (Greedy / Matrix)

English

中文

Comments