Monotone Increasing Digits问题及解法

问题描述：

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.

(Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)

示例:

Input: N = 10
Output: 9

Input: N = 1234
Output: 1234

Input: N = 332
Output: 299

Note: N is an integer in the range [0, 10^9].

问题分析：

从左到右找到相邻两个数字中digit[i] > digit[i+1]的索引i，对于i+1到digits.size()的数字全部置为9；

对于j在i到0之间依次找到digits[j] > digits[j + 1]，设置digits[j + 1] = 9;digits[j]--;其他情况直接跳出循环。

过程详见代码：

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        int n = N;
		if (N < 10) return N;
		if (N == 10) return 9;
		vector<int> digits;
		while (N)
		{
			digits.push_back(N % 10);
			N /= 10;
		}
		reverse(digits.begin(), digits.end());
		int i = 0;
		for (; i < digits.size() - 1; i++)
		{
			if (digits[i] > digits[i + 1])
			{
				digits[i]--;
				break;
			}
		}
		if (i == digits.size()) return n;
		for (int j = i + 1; j < digits.size(); j++) digits[j] = 9;
		for (int j = i - 1; j >= 0; j--)
		{
			if (digits[j] > digits[j + 1])
			{
				digits[j + 1] = 9;
				digits[j]--;
			}
			else break;
		}
		int res = 0;
		for (int t = 0; t < digits.size(); t++)
		{
			res = res * 10 + digits[t];
		}
		return res;
    }
};