mirror of
https://github.com/youngyangyang04/leetcode-master.git
synced 2026-02-02 18:39:09 +08:00
443 lines
13 KiB
Markdown
Executable File
443 lines
13 KiB
Markdown
Executable File
* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html)
|
||
* [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html)
|
||
* [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html)
|
||
|
||
|
||
# 738.单调递增的数字
|
||
[力扣题目链接](https://leetcode.cn/problems/monotone-increasing-digits/)
|
||
|
||
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
|
||
|
||
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
|
||
|
||
示例 1:
|
||
* 输入: N = 10
|
||
* 输出: 9
|
||
|
||
示例 2:
|
||
* 输入: N = 1234
|
||
* 输出: 1234
|
||
|
||
示例 3:
|
||
* 输入: N = 332
|
||
* 输出: 299
|
||
|
||
说明: N 是在 [0, 10^9] 范围内的一个整数。
|
||
|
||
## 算法公开课
|
||
|
||
**[《代码随想录》算法视频公开课](https://programmercarl.com/other/gongkaike.html)：[贪心算法，思路不难想，但代码不好写！LeetCode:738.单调自增的数字](https://www.bilibili.com/video/BV1Kv4y1x7tP)，相信结合视频在看本篇题解，更有助于大家对本题的理解**。
|
||
|
||
## 思路
|
||
|
||
|
||
### 暴力解法
|
||
|
||
题意很简单，那么首先想的就是暴力解法了，来我替大家暴力一波，结果自然是超时！
|
||
|
||
代码如下：
|
||
```CPP
|
||
class Solution {
|
||
private:
|
||
// 判断一个数字的各位上是否是递增
|
||
bool checkNum(int num) {
|
||
int max = 10;
|
||
while (num) {
|
||
int t = num % 10;
|
||
if (max >= t) max = t;
|
||
else return false;
|
||
num = num / 10;
|
||
}
|
||
return true;
|
||
}
|
||
public:
|
||
int monotoneIncreasingDigits(int N) {
|
||
for (int i = N; i > 0; i--) { // 从大到小遍历
|
||
if (checkNum(i)) return i;
|
||
}
|
||
return 0;
|
||
}
|
||
};
|
||
```
|
||
* 时间复杂度：O(n × m) m为n的数字长度
|
||
* 空间复杂度：O(1)
|
||
|
||
### 贪心算法
|
||
|
||
题目要求小于等于N的最大单调递增的整数，那么拿一个两位的数字来举例。
|
||
|
||
例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。
|
||
|
||
这一点如果想清楚了，这道题就好办了。
|
||
|
||
此时是从前向后遍历还是从后向前遍历呢？
|
||
|
||
从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。
|
||
|
||
这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。
|
||
|
||
那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299
|
||
|
||
确定了遍历顺序之后，那么此时局部最优就可以推出全局，找不出反例，试试贪心。
|
||
|
||
C++代码如下：
|
||
|
||
```CPP
|
||
class Solution {
|
||
public:
|
||
int monotoneIncreasingDigits(int N) {
|
||
string strNum = to_string(N);
|
||
// flag用来标记赋值9从哪里开始
|
||
// 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
|
||
int flag = strNum.size();
|
||
for (int i = strNum.size() - 1; i > 0; i--) {
|
||
if (strNum[i - 1] > strNum[i] ) {
|
||
flag = i;
|
||
strNum[i - 1]--;
|
||
}
|
||
}
|
||
for (int i = flag; i < strNum.size(); i++) {
|
||
strNum[i] = '9';
|
||
}
|
||
return stoi(strNum);
|
||
}
|
||
};
|
||
|
||
```
|
||
|
||
* 时间复杂度：O(n)，n 为数字长度
|
||
* 空间复杂度：O(n)，需要一个字符串，转化为字符串操作更方便
|
||
|
||
## 总结
|
||
|
||
本题只要想清楚个例，例如98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]减一，strNum[i]赋值9，这样这个整数就是89。就可以很自然想到对应的贪心解法了。
|
||
|
||
想到了贪心，还要考虑遍历顺序，只有从后向前遍历才能重复利用上次比较的结果。
|
||
|
||
最后代码实现的时候，也需要一些技巧，例如用一个flag来标记从哪里开始赋值9。
|
||
|
||
|
||
## 其他语言版本
|
||
|
||
|
||
### Java
|
||
```java
|
||
版本1
|
||
class Solution {
|
||
public int monotoneIncreasingDigits(int N) {
|
||
String[] strings = (N + "").split("");
|
||
int start = strings.length;
|
||
for (int i = strings.length - 1; i > 0; i--) {
|
||
if (Integer.parseInt(strings[i]) < Integer.parseInt(strings[i - 1])) {
|
||
strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";
|
||
start = i;
|
||
}
|
||
}
|
||
for (int i = start; i < strings.length; i++) {
|
||
strings[i] = "9";
|
||
}
|
||
return Integer.parseInt(String.join("",strings));
|
||
}
|
||
}
|
||
```
|
||
java版本1中创建了String数组，多次使用Integer.parseInt了方法，这导致不管是耗时还是空间占用都非常高，用时12ms，下面提供一个版本在char数组上原地修改，用时1ms的版本
|
||
```java
|
||
版本2
|
||
class Solution {
|
||
public int monotoneIncreasingDigits(int n) {
|
||
String s = String.valueOf(n);
|
||
char[] chars = s.toCharArray();
|
||
int start = s.length();
|
||
for (int i = s.length() - 2; i >= 0; i--) {
|
||
if (chars[i] > chars[i + 1]) {
|
||
chars[i]--;
|
||
start = i+1;
|
||
}
|
||
}
|
||
for (int i = start; i < s.length(); i++) {
|
||
chars[i] = '9';
|
||
}
|
||
return Integer.parseInt(String.valueOf(chars));
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
### Python
|
||
暴力
|
||
```python
|
||
class Solution:
|
||
def checkNum(self, num):
|
||
max_digit = 10
|
||
while num:
|
||
digit = num % 10
|
||
if max_digit >= digit:
|
||
max_digit = digit
|
||
else:
|
||
return False
|
||
num //= 10
|
||
return True
|
||
|
||
def monotoneIncreasingDigits(self, N):
|
||
for i in range(N, 0, -1):
|
||
if self.checkNum(i):
|
||
return i
|
||
return 0
|
||
|
||
```
|
||
贪心（版本一）
|
||
```python
|
||
class Solution:
|
||
def monotoneIncreasingDigits(self, n: int) -> int:
|
||
# 将整数转换为字符串
|
||
strNum = str(n)
|
||
# flag用来标记赋值9从哪里开始
|
||
# 设置为字符串长度，为了防止第二个for循环在flag没有被赋值的情况下执行
|
||
flag = len(strNum)
|
||
|
||
# 从右往左遍历字符串
|
||
for i in range(len(strNum) - 1, 0, -1):
|
||
# 如果当前字符比前一个字符小，说明需要修改前一个字符
|
||
if strNum[i - 1] > strNum[i]:
|
||
flag = i # 更新flag的值，记录需要修改的位置
|
||
# 将前一个字符减1，以保证递增性质
|
||
strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + strNum[i:]
|
||
|
||
# 将flag位置及之后的字符都修改为9，以保证最大的递增数字
|
||
for i in range(flag, len(strNum)):
|
||
strNum = strNum[:i] + '9' + strNum[i + 1:]
|
||
|
||
# 将最终的字符串转换回整数并返回
|
||
return int(strNum)
|
||
|
||
```
|
||
贪心（版本二）
|
||
```python
|
||
class Solution:
|
||
def monotoneIncreasingDigits(self, n: int) -> int:
|
||
# 将整数转换为字符串
|
||
strNum = list(str(n))
|
||
|
||
# 从右往左遍历字符串
|
||
for i in range(len(strNum) - 1, 0, -1):
|
||
# 如果当前字符比前一个字符小，说明需要修改前一个字符
|
||
if strNum[i - 1] > strNum[i]:
|
||
strNum[i - 1] = str(int(strNum[i - 1]) - 1) # 将前一个字符减1
|
||
# 将修改位置后面的字符都设置为9，因为修改前一个字符可能破坏了递增性质
|
||
for j in range(i, len(strNum)):
|
||
strNum[j] = '9'
|
||
|
||
# 将列表转换为字符串，并将字符串转换为整数并返回
|
||
return int(''.join(strNum))
|
||
|
||
|
||
```
|
||
贪心（版本三）
|
||
|
||
```python
|
||
class Solution:
|
||
def monotoneIncreasingDigits(self, n: int) -> int:
|
||
# 将整数转换为字符串
|
||
strNum = list(str(n))
|
||
|
||
# 从右往左遍历字符串
|
||
for i in range(len(strNum) - 1, 0, -1):
|
||
# 如果当前字符比前一个字符小，说明需要修改前一个字符
|
||
if strNum[i - 1] > strNum[i]:
|
||
strNum[i - 1] = str(int(strNum[i - 1]) - 1) # 将前一个字符减1
|
||
# 将修改位置后面的字符都设置为9，因为修改前一个字符可能破坏了递增性质
|
||
strNum[i:] = '9' * (len(strNum) - i)
|
||
|
||
# 将列表转换为字符串，并将字符串转换为整数并返回
|
||
return int(''.join(strNum))
|
||
|
||
```
|
||
贪心（版本四）精简
|
||
|
||
```python
|
||
class Solution:
|
||
def monotoneIncreasingDigits(self, n: int) -> int:
|
||
strNum = str(n)
|
||
for i in range(len(strNum) - 1, 0, -1):
|
||
# 如果当前字符比前一个字符小，说明需要修改前一个字符
|
||
if strNum[i - 1] > strNum[i]:
|
||
# 将前一个字符减1，以保证递增性质
|
||
# 使用字符串切片操作将修改后的前面部分与后面部分进行拼接
|
||
strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + '9' * (len(strNum) - i)
|
||
return int(strNum)
|
||
|
||
|
||
```
|
||
### Go
|
||
```go
|
||
func monotoneIncreasingDigits(n int) int {
|
||
s := strconv.Itoa(n)
|
||
// 从左到右遍历字符串，找到第一个不满足单调递增的位置
|
||
for i := len(s) - 2; i >= 0; i-- {
|
||
if s[i] > s[i+1] {
|
||
// 将该位置的数字减1
|
||
s = s[:i] + string(s[i]-1) + s[i+1:]
|
||
// 将该位置之后的所有数字置为9
|
||
for j := i + 1; j < len(s); j++ {
|
||
s = s[:j] + "9" + s[j+1:]
|
||
}
|
||
}
|
||
}
|
||
result, _ := strconv.Atoi(s)
|
||
return result
|
||
}
|
||
```
|
||
|
||
### JavaScript
|
||
```Javascript
|
||
var monotoneIncreasingDigits = function(n) {
|
||
n = n.toString()
|
||
n = n.split('').map(item => {
|
||
return +item
|
||
})
|
||
let flag = Infinity
|
||
for(let i = n.length - 1; i > 0; i--) {
|
||
if(n [i - 1] > n[i]) {
|
||
flag = i
|
||
n[i - 1] = n[i - 1] - 1
|
||
n[i] = 9
|
||
}
|
||
}
|
||
|
||
for(let i = flag; i < n.length; i++) {
|
||
n[i] = 9
|
||
}
|
||
|
||
n = n.join('')
|
||
return +n
|
||
};
|
||
```
|
||
|
||
### TypeScript
|
||
|
||
```typescript
|
||
function monotoneIncreasingDigits(n: number): number {
|
||
let strArr: number[] = String(n).split('').map(i => parseInt(i));
|
||
const length = strArr.length;
|
||
let flag: number = length;
|
||
for (let i = length - 2; i >= 0; i--) {
|
||
if (strArr[i] > strArr[i + 1]) {
|
||
strArr[i] -= 1;
|
||
flag = i + 1;
|
||
}
|
||
}
|
||
for (let i = flag; i < length; i++) {
|
||
strArr[i] = 9;
|
||
}
|
||
return parseInt(strArr.join(''));
|
||
};
|
||
```
|
||
|
||
|
||
### Scala
|
||
|
||
直接转换为了整数数组:
|
||
```scala
|
||
object Solution {
|
||
import scala.collection.mutable
|
||
def monotoneIncreasingDigits(n: Int): Int = {
|
||
var digits = mutable.ArrayBuffer[Int]()
|
||
// 提取每位数字
|
||
var temp = n // 因为 参数n 是不可变量所以需要赋值给一个可变量
|
||
while (temp != 0) {
|
||
digits.append(temp % 10)
|
||
temp = temp / 10
|
||
}
|
||
// 贪心
|
||
var flag = -1
|
||
for (i <- 0 until (digits.length - 1) if digits(i) < digits(i + 1)) {
|
||
flag = i
|
||
digits(i + 1) -= 1
|
||
}
|
||
for (i <- 0 to flag) digits(i) = 9
|
||
|
||
// 拼接
|
||
var res = 0
|
||
for (i <- 0 until digits.length) {
|
||
res += digits(i) * math.pow(10, i).toInt
|
||
}
|
||
res
|
||
}
|
||
}
|
||
```
|
||
|
||
### Rust
|
||
|
||
```Rust
|
||
impl Solution {
|
||
pub fn monotone_increasing_digits(n: i32) -> i32 {
|
||
let mut n_bytes = n.to_string().into_bytes();
|
||
let mut flag = n_bytes.len();
|
||
for i in (1..n_bytes.len()).rev() {
|
||
if n_bytes[i - 1] > n_bytes[i] {
|
||
flag = i;
|
||
n_bytes[i - 1] -= 1;
|
||
}
|
||
}
|
||
for v in n_bytes.iter_mut().skip(flag) {
|
||
*v = 57;
|
||
}
|
||
n_bytes
|
||
.into_iter()
|
||
.fold(0, |acc, x| acc * 10 + x as i32 - 48)
|
||
}
|
||
}
|
||
```
|
||
### C
|
||
|
||
```c
|
||
int monotoneIncreasingDigits(int n) {
|
||
char str[11];
|
||
// 将数字转换为字符串
|
||
sprintf(str, "%d", n);
|
||
int len = strlen(str);
|
||
int flag = strlen(str);
|
||
for(int i = len - 1; i > 0; i--){
|
||
if(str[i] < str[i - 1]){
|
||
str[i - 1]--;
|
||
flag = i;
|
||
}
|
||
}
|
||
for(int i = flag; i < len; i++){
|
||
str[i] = '9';
|
||
}
|
||
// 字符串转数字
|
||
return atoi(str);
|
||
}
|
||
```
|
||
|
||
|
||
|
||
### C#
|
||
|
||
```csharp
|
||
public class Solution
|
||
{
|
||
public int MonotoneIncreasingDigits(int n)
|
||
{
|
||
char[] s = n.ToString().ToCharArray();
|
||
int flag = s.Length;
|
||
for (int i = s.Length - 1; i > 0; i--)
|
||
{
|
||
if (s[i - 1] > s[i])
|
||
{
|
||
flag = i;
|
||
s[i - 1]--;
|
||
}
|
||
}
|
||
for (int i = flag; i < s.Length; i++)
|
||
{
|
||
s[i] = '9';
|
||
}
|
||
return int.Parse(new string(s));
|
||
}
|
||
}
|
||
```
|
||
|
||
|