738. 单调递增的数字

[yankewei]

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

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

示例 1:

输入: N = 10
输出: 9

示例 2:

输入: N = 1234
输出: 1234

示例 3:

输入: N = 332
输出: 299

说明: N 是在 [0, 10^9] 范围内的一个整数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/monotone-increasing-digits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[yankewei]

我觉得这个题目最重要的就是理解单调递增的含义以及单调递增的最大值。假如有一个数字123454，把它改为单调递增的最大值就是123449。就是从前往后遍历，如果当前数字比下一个数字大，那么当前数字应该-1，后边的数字改为9即可。但是存在一个问题就是，如果当前数字减1之后比前一个数字小，比如332，按照上边的逻辑改完之后是329，不符合题目要求，因为2<3，那么需要把2改为9，3改为2，就是299。

func monotoneIncreasingDigits(N int) int {
    s := []byte(strconv.Itoa(N))
    var i int
    b := false
    for i = 0; i < len(s)-1; i++ {
	if s[i] > s[i+1] {
	    b = true
	    break
	}
    }

    if !b {
	return N
    }

    // 把 i 之边的所有元素都设置为9
    for k := i + 1; k < len(s); k++ {
	s[k] = '9'
    }
    // 设置当前 i 的元素减去1
    s[i] = s[i] - 1
    // 设置i之前的元素
    for k := i; k > 0; k-- {
	if s[k] < s[k-1] {
	    s[k] = '9'
	    s[k-1] = s[k-1] - 1
	}
    }
    ans, _ := strconv.Atoi(string(s))
    return ans
}