What is the main pattern in Minimum Operations to Make Columns Strictly Increasing?

The problem uses a greedy choice plus invariant validation pattern, ensuring each cell exceeds the one above it with minimal increments.

Can I process rows instead of columns?

No, the problem specifically requires strictly increasing columns; row processing would violate the intended pattern.

How do I handle equal consecutive values in a column?

Increment the lower or equal value minimally so it becomes strictly greater than the one above, counting the increments toward the total.

What is the optimal time complexity for this problem?

O(m * n) since each cell must be checked once per column to maintain the strictly increasing invariant.

Does this approach work for large matrices?

Yes, it scales linearly with m * n, but extremely large matrices may require careful iteration to avoid timeouts.

#3402

Easy

auto_awesome贪心·invariant

LeetCode 题解工作台

使每一列严格递增的最少操作次数

给你一个由非负整数组成的 m x n 矩阵 grid 。在一次操作中，你可以将任意元素 grid[i][j] 的值增加 1。返回使 grid 的所有列严格递增所需的最少操作次数。示例 1：输入: grid = [[3,2],[1,3],[3,4],[0,1]] 输出: 15 解释…

数组贪心矩阵

题目描述

给你一个由非负整数组成的 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

lightbulb

解题思路

方法一：逐列计算

我们可以逐列遍历矩阵，对于每一列，我们可以计算出使其严格递增所需的最少操作次数。具体地，对于每一列，我们可以维护一个变量 $\textit{pre}$ ，表示当前列中前一个元素的值。然后，我们从上到下遍历当前列，对于当前元素 $\textit{cur}$ ，如果 $\textit{pre} < \textit{cur}$ ，则说明当前元素已经大于前一个元素，我们只需要更新 $\textit{pre} = \textit{cur}$ ；否则，我们需要将当前元素增加到 $\textit{pre} + 1$ ，并将增加的次数累加到答案中。

时间复杂度 $O(m \times n)$ ，其中 $m$ 和 $n$ 分别是矩阵 $\textit{grid}$ 的行数和列数。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def minimumOperations(self, grid: List[List[int]]) -> int:
        ans = 0
        for col in zip(*grid):
            pre = -1
            for cur in col:
                if pre < cur:
                    pre = cur
                else:
                    pre += 1
                    ans += pre - cur
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(m * n) since each cell is visited once per column. Space complexity is O(1) beyond input storage, as only running totals are maintained.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate identifies a per-column approach and avoids unnecessary row comparisons across columns.
question_mark
They correctly implement minimal increments instead of blindly adding arbitrary values.
question_mark
They justify why processing top-down ensures the greedy invariant holds for all subsequent rows.

warning

常见陷阱

外企场景

error
Incrementing cells without checking the previous row can violate the strictly increasing requirement.
error
Attempting to modify rows simultaneously may overcount operations.
error
Neglecting edge cases where multiple rows have equal values leads to incorrect totals.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing decrements as well as increments to achieve strictly increasing columns.
arrow_right_alt
Finding minimum operations for strictly increasing rows instead of columns.
arrow_right_alt
Handling larger matrices with m, n up to 10^3, requiring optimized traversal.

help

常见问题

外企场景

继续练习

#3462 提取至多 K 个元素的最大总和 #2931 购买物品的最大开销 #2573 找出对应 LCP 矩阵的字符串