问题描述
一个正整数如果任何一个数位不大于右边相邻的数位，则称为一个数位递增的数，例如1135是一个数位递增的数，而1024不是一个数位递增的数。
给定正整数 n，请问在整数 1 至 n 中有多少个数位递增的数？
输入格式
输入的第一行包含一个整数 n。
输出格式
输出一行包含一个整数，表示答案。
样例输入
30
样例输出
26
评测用例规模与约定
对于 40% 的评测用例，1 <= n <= 1000。
对于 80% 的评测用例，1 <= n <= 100000。
对于所有评测用例，1 <= n <= 1000000。
package 第十三次模拟;
import
在编程竞赛中，如蓝桥杯，经常遇到各种数学和逻辑问题，其中之一是寻找数位递增的数。本问题的描述是找到从1到给定整数n之间有多少个数位递增的数。一个数位递增的数是指其每一位数字都不大于其右侧的数字，比如1135是一个递增数，而1024则不是，因为4大于2。
题目给出了输入和输出的格式。输入是一个整数n，输出是符合条件的递增数的数量。样例输入是30，输出是26。对于不同级别的评测用例，n的范围有所不同，但最大不超过1000000。
解决这个问题，我们可以采用深度优先搜索（DFS）的方法。代码中定义了两个静态变量，n用于存储给定的整数，count记录递增数的总数。在main函数中，首先读取输入的n值，然后调用递归函数f进行搜索，最后输出结果（减去1是因为包括了0，但题目要求的是正整数）。
函数f接受两个参数，num表示当前构建的递增数，temp表示下一个可能添加的数字。在函数内部，如果num超过n，则返回；否则，增加count并继续对下一个数字进行尝试。通过for循环遍历从temp到9的所有数字，将每个数字加到num的末尾，并递归调用f。
这段代码的时间复杂度为O(n)，因为它需要检查n个数。空间复杂度为O(logn)，因为在最坏情况下，需要递归log10n层，因为每个数最多有10个可能的数位。由于n的最大值为1000000，这个算法可以在合理的时间内解决问题，满足了评测用例的规模要求。
这个Java程序利用深度优先搜索策略解决了蓝桥杯中数位递增数的问题，有效地处理了不同规模的输入数据。通过递归和计数，程序能够找出1到n之间的所有递增数，并输出它们的总数。这种方法简洁且易于理解，适用于解决此类计数问题。
