单调递增的数字1

单调递增的数字是指每一位数字都比其左边的数字大或者相等的整数，例如1234、299。这个问题是LeetCode上的一道题目，要求找到小于或等于给定非负整数N的单调递增的最大整数。 解决这个问题的一种方法是采用分治的思想，递归地处理整数的每一位。以下是一个简单的C++实现： ```cpp int monotoneIncreasingDigits(int N) { // 如果N为0，返回0 if (N == 0) return 0; // 获取个位数和十位数 int r = N % 10; // 个位 N /= 10; int l = N % 10; // 十位 // 如果个位数小于十位数，说明需要在前面的位置寻找单调递增的数字 if (r < l) { // 将当前数字减1，得到前一位的单调递增最大值 N--; } // 递归求解N的单调递增最大值 int ans = monotoneIncreasingDigits(N); // 如果原来的数字比递归后的数字大，说明个位数可以设置为9，以保证单调递增 if (N > ans) { ans = ans * 10 + 9; } else { // 否则，保持个位数不变 ans = ans * 10 + r; } return ans; } ``` 在这个算法中，首先检查个位和十位的关系，如果个位小于十位，说明在当前数的左边存在一个更大的单调递增数，因此将当前数减1，然后对新的数再次进行递归调用。递归结束后，根据原数与递归结果的大小关系决定个位是保留还是设为9，以保证单调递增性。 例如，对于输入332，算法会先比较2和3，发现2小于3，于是将332减1得到331，然后递归处理33。在处理33时，发现33已经是单调递增的，所以返回33。由于332大于33，所以个位设为9，得到单调递增的最大数299。 这个算法的时间复杂度为O(logN)，因为每次操作都是在分割数字的位数上进行，而位数最多是log10(N)。空间复杂度也是O(logN)，因为递归深度最多为log10(N)。这是一种有效的解决方案，能够快速找到符合条件的单调递增的最大整数。