【玩转贪心算法专题】738. 单调递增的数字【中等】
【玩转贪心算法专题】738. 单调递增的数字【中等】
1、力扣链接
https://leetcode.cn/problems/monotone-increasing-digits/description/
2、题目描述
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:
输入: n = 10
输出: 9
示例 2:
输入: n = 1234
输出: 1234
示例 3:
输入: n = 332
输出: 299
提示:
0 <= n <= 109
3、题目分析
对于贪心算法的题目，可从 寻求局部最优解入手，以局部最优解，得到全局最优解
本题思路：
判断两数之间是否单调递增，如果不是则需要变化，将前一个数-1，后面全部置为9，但要主要需从后往前遍历
例如：332
如果从前往后遍历，第一次 33，没问题，第二次32，需要改为 329，但发现329其实并不能满足单调递增
4、代码实现
1、Java
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;}}while(start<strings.length){strings[start] ="9";start++;}return Integer.parseInt(String.join("",strings));}
}
2、C++
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);}
};3、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)
4、go
func monotoneIncreasingDigits(N int) int {s := strconv.Itoa(N)//将数字转为字符串，方便使用下标ss := []byte(s)//将字符串转为byte数组，方便更改。n := len(ss)if n <= 1 {return N}for i := n-1; i > 0; i-- {if ss[i-1] > ss[i] { //前一个大于后一位,前一位减1，后面的全部置为9ss[i-1] -= 1for j := i; j < n; j++ { //后面的全部置为9ss[j] = '9'}} }res, _ := strconv.Atoi(string(ss))return res
}