单调递增编程怎么写

时间:2025-01-23 03:43:35 游戏攻略

要实现一个单调递增的整数,其各个位数上的数字也是单调递增的,可以使用贪心算法。以下是一个可能的实现方法:

1. 将整数转换为字符数组,以便于从后向前遍历。

2. 从后向前遍历字符数组,找到第一个不满足单调递增的位置。

3. 将该位置的数字减1,并将该位置之后的所有数字都设置为9。

4. 将修改后的字符数组转换回整数并返回。

```java

class Solution {

public int monotoneIncreasingDigits(int n) {

char[] digits = String.valueOf(n).toCharArray();

int flag = digits.length;

// 从后向前遍历,找到第一个不满足单调递增的位置

for (int i = digits.length - 1; i > 0; i--) {

if (digits[i] < digits[i - 1]) {

flag = i;

digits[i - 1]--;

}

}

// 将flag位置之后的所有数字都设置为9

for (int i = flag; i < digits.length; i++) {

digits[i] = '9';

}

return Integer.parseInt(new String(digits));

}

}

```

解释

转换为字符数组 :`char[] digits = String.valueOf(n).toCharArray();`

将整数`n`转换为字符数组,便于从后向前遍历。

找到第一个不满足单调递增的位置

```java

for (int i = digits.length - 1; i > 0; i--) {

if (digits[i] < digits[i - 1]) {

flag = i;

digits[i - 1]--;

}

}

```

从后向前遍历字符数组,找到第一个不满足单调递增的位置`i`,并将该位置的数字减1,同时记录该位置为`flag`。

将flag位置之后的所有数字都设置为9

```java

for (int i = flag; i < digits.length; i++) {

digits[i] = '9';

}

```

将flag位置之后的所有数字都设置为9,以确保结果是一个单调递增的整数。

转换回整数

```java

return Integer.parseInt(new String(digits));

```

将修改后的字符数组转换回整数并返回。

这个方法的时间复杂度是O(logN),因为我们需要遍历整数的每一位。空间复杂度是O(logN),因为我们需要存储整数的字符数组。