minimum-operations-to-make-columns-strictly-increasing

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given a <code>m x n</code> matrix <code>grid</code> consisting of non-negative integers.

In one operation, you can increment the value of any <code>grid[i][j]</code> by 1.

Return the minimum number of operations needed to make all columns of <code>grid</code> strictly increasing.

&nbsp;
Example 1:

<div class="example-block">
Input: grid = [[3,2],[1,3],[3,4],[0,1]]

Output: 15

Explanation:

<ul>
	<li>To make the <code>0th</code> column strictly increasing, we can apply 3 operations on <code>grid[1][0]</code>, 2 operations on <code>grid[2][0]</code>, and 6 operations on <code>grid[3][0]</code>.</li>
	<li>To make the <code>1st</code> column strictly increasing, we can apply 4 operations on <code>grid[3][1]</code>.</li>
</ul>
<img alt="" src="https://assets.leetcode.com/uploads/2024/11/10/firstexample.png" style="width: 200px; height: 347px;" /></div>

Example 2:

<div class="example-block">
Input: grid = [[3,2,1],[2,1,0],[1,2,3]]

Output: 12

Explanation:

<ul>
	<li>To make the <code>0th</code> column strictly increasing, we can apply 2 operations on <code>grid[1][0]</code>, and 4 operations on <code>grid[2][0]</code>.</li>
	<li>To make the <code>1st</code> column strictly increasing, we can apply 2 operations on <code>grid[1][1]</code>, and 2 operations on <code>grid[2][1]</code>.</li>
	<li>To make the <code>2nd</code> column strictly increasing, we can apply 2 operations on <code>grid[1][2]</code>.</li>
</ul>
<img alt="" src="https://assets.leetcode.com/uploads/2024/11/10/secondexample.png" style="width: 300px; height: 257px;" /></div>

&nbsp;
Constraints:

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 50</code></li>
	<li><code>0 &lt;= grid[i][j] &lt; 2500</code></li>
</ul>

&nbsp;
<div class="spoiler">
<div>
<pre>

&nbsp;</pre>
</div>
</div>

第 430 场周赛

weekly-contest-430

minimumOperations

中级工程师

Minimum Operations to Make Columns Strictly Increasing

Minimum Operations to Make the Array Increasing

minimum-operations-to-make-the-array-increasing

最少操作使数组递增

Greedy

Array

Matrix

给你一个由&nbsp;非负&nbsp;整数组成的 <code>m x n</code> 矩阵 <code>grid</code>。

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

返回使 <code>grid</code> 的所有列&nbsp;严格递增&nbsp;所需的&nbsp;最少&nbsp;操作次数。

&nbsp;

示例 1：

<div class="example-block">
输入: grid = [[3,2],[1,3],[3,4],[0,1]]

输出: 15

解释:

<ul>
	<li>为了让第 <code>0</code>&nbsp;列严格递增，可以对 <code>grid[1][0]</code> 执行 3 次操作，对 <code>grid[2][0]</code> 执行 2 次操作，对 <code>grid[3][0]</code> 执行 6 次操作。</li>
	<li>为了让第 <code>1</code>&nbsp;列严格递增，可以对 <code>grid[3][1]</code> 执行 4 次操作。</li>
</ul>
<img alt="" src="https://assets.leetcode.com/uploads/2024/11/10/firstexample.png" style="width: 200px; height: 347px;" /></div>

示例 2：

<div class="example-block">
输入: grid = [[3,2,1],[2,1,0],[1,2,3]]

输出: 12

解释:

<ul>
	<li>为了让第 <code>0</code>&nbsp;列严格递增，可以对 <code>grid[1][0]</code> 执行 2 次操作，对 <code>grid[2][0]</code> 执行 4 次操作。</li>
	<li>为了让第 <code>1</code>&nbsp;列严格递增，可以对 <code>grid[1][1]</code> 执行 2 次操作，对 <code>grid[2][1]</code> 执行 2 次操作。</li>
	<li>为了让第 <code>2</code>&nbsp;列严格递增，可以对 <code>grid[1][2]</code> 执行 2 次操作。</li>
</ul>
<img alt="" src="https://assets.leetcode.com/uploads/2024/11/10/secondexample.png" style="width: 300px; height: 257px;" /></div>

&nbsp;

提示:

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 50</code></li>
	<li><code>0 &lt;= grid[i][j] &lt; 2500</code></li>
</ul>