目录

力扣738. 单调递增的数字

解析代码

---

力扣738. 单调递增的数字

738. 单调递增的数字

难度 中等

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

提示:

• 0 <= n <= 10^9

class Solution {
public:int monotoneIncreasingDigits(int n) {}
};

---

解析代码

下面是暴力的代码（会超时，因为找一个数的数位是logN的，总时间是O（N*logN））

class Solution {
public:int monotoneIncreasingDigits(int n) {for(int i = n; i >= 0; --i){string str = to_string(i);int j = 1, sz = str.size();bool flag = true;for(; j < sz; ++j){if(str[j] < str[j - 1]){flag = false;break;}}if(flag)return i;}return 9;}
};

---

贪心策略： 假设有一个数 n，它有 m 位数字，每一位数字分别是 d.1, d.2 , ..., dm 。

        想要修改这个数字，使得修改后的结果既小于原数字 n ，又满足单调递增和最大化。为了实现这个目标，我们需要将不满足递增的高位数字尽可能地减小。

        首先需要找到一个位置 k，使得d.1 ≤ d.2 ≤ ... ≤ d.k > d.k+1 ... （例如：12335412，k=4，d.k=5）。这个位置 k 表示从高到低，第一个不满足单调递增的数字的位置。我们需要将这个数字 减1，因为这是最小的减小量。

        接下来需要将低位数字都修改为9，这样可以保证修改后的数字是最大的，并且还能保证单调递增。但是要处理找到第一个不满足单调递增的数字的位置，前面数字和此sh大小相等的情况（还是上面的k）：

        需要继续修改这个数字。需要找到一个位置 t ，使得d.1 ≤ d.2 ≤ ... < d.t = d.t+1 = ... = d.k。这个位置 t 表示从高到低，最后一个高位数字相等的位置。我们需要将 d.t 减 1，并将之后的所有数字都修改为9，以满足d.1 ≤ d.2 ≤ ... ≤ d.t − 1 ≤ 9 ≤ ... ≤ 9，即高位数字的单调递增和低位数字的最大化。例如：1224444361，成功修改后的最大值为1223999999。

通过这种修改方式，可以得到一个新的数字，它既小于原数字 n，又满足单调递增和最大化。

class Solution {
public:int monotoneIncreasingDigits(int n) {string s = to_string(n);int i = 0, m = s.size();while(i + 1 < m && s[i] <= s[i + 1])i++; // 找第⼀个递减的位置if(i == m - 1) // 如果没有递减的return n; while(i - 1 >= 0 && s[i] == s[i - 1])--i; // 回推--s[i]; // 开始修改for(int j = i + 1; j < m; ++j)s[j] = '9';return stoi(s);}
};