【力扣】738. 单调递增的数字

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

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

示例 1：

输入: n = 10
输出: 9

示例 2：

输入: n = 1234
输出: 1234

示例 3：

输入: n = 332
输出: 299

提示:

• 0 <= n <= 109

题解：

贪心算法：

func monotoneIncreasingDigits(n int) int {
	str := []byte(strconv.Itoa(n))
	flag := len(str)
	// 从右往左逐个数字进行遍历
	for i := len(str) - 1; i > 0; i-- {
		// 判断右边的数字是不是大于左边的数字
		if str[i-1] > str[i] {
			// 左边的数字-1 同时标记从哪一位开始后面都是9
			str[i-1]--
			flag = i
		}
	}
	// 处理标记，标记往后的数字都是9
	for i := flag; i < len(str); i++ {
		str[i] = '9'
	}
	// 从字符转换为数字
	result, _ := strconv.Atoi(string(str))
	return result
}