企业官网建设流程全解析

原题：力扣738：单调递增的数字。要求找到不超过n的最大整数，且十进制相邻位满足前一位不大于后一位；输入范围为0 <= n <= 10^9。

题目说“递增”，但这里允许相等，所以1123也合法。

我原来的解法不是从右往左逐位修改，而是：从左往右找第一个下降点，再回退到相同数字连续区域的最左端，减一，后缀全部填9。

代码不长，真正值得解释的是：为什么只回退相同数字？为什么后面可以全部填9？

1. 先保留原来的手写过程

这张图保留的是当时的尝试和批注，不是每一步都标清的标准推导。下面用完整的中间状态把其中两个输入讲清楚。

对于1242，第一次下降发生在4 > 2：

1 2 4 2 ^ 第一个下降点左侧 1 2 3 9 将4减一，后缀填9

2 <= 3仍成立，所以不用再向左改。

对于332，如果只把第二个3减一，会得到：

3 3 2 ^ 找到3 > 2 3 2 9 只修改这里，前面又出现3 > 2：不合法

因此必须先回退整个连续的3，再修改：

3 3 2 ^ 回退到连续相同数字的最左端 2 9 9 减一，后面的位全部填9

回退不是为了“让高位出现更多9”而随意改变前缀。它首先是为了保证减一之后，前缀仍然满足单调条件。

2. 为什么只需要越过相同数字？

设第一个下降点左侧数字为x。下降点之前没有下降，所以此前前缀已经非递减。

如果前一位也是x，当前位减一后就变成x > x-1，因此要继续向左。

一直回到连续x区域的开头：若还有前一位，它一定严格小于x。十进制数字是整数，于是它至多为x-1，当前位减一之后仍满足单调条件。

例如1332，连续3的左侧是1：

1 3 3 2 -> 1 2 9 9 ^

不必再把前面的1也减掉。那样会不必要地让结果更小。

3. 为什么这一改动还能保证最大？

同位数数字比较大小，第一处不同的位决定顺序。要在不超过n的前提下尽量大，就应尽量保留左侧前缀，尽量晚地发生减小。

只修改下降点之后的位，无法消除已经保留的下降关系；在连续x区域内部才首次减小，又会与前面的x冲突。所以最晚的合法首次减小位置，就是这段相同数字的开头。

在这个位置只减1，保留最大的可行前缀。前缀已经严格小于原数，后缀再大也不会超过n；全部填9既最大，也满足非递减。

先确定“最晚能改哪一位”，再确定“这一位最多留多大”，最后让后缀最大。这是原代码背后的贪心理由，不只是样例碰巧通过。

4. 原来的Java算法

下面保留原算法，只调整注释。字符减一操作在这里成立，是因为输入非负，下降点左侧的数字必然大于后面的数字，因此不会从字符0再减成非数字。

class Solution { public int monotoneIncreasingDigits(int n) { char[] s = Integer.toString(n).toCharArray(); int i = 0, m = s.length; while (i + 1 < m && s[i] <= s[i + 1]) i++; if (i == m - 1) return n; while (i - 1 >= 0 && s[i] == s[i - 1]) i--; s[i]--; for (int j = i + 1; j < m; j++) s[j] = '9'; return Integer.parseInt(new String(s)); } }

10会得到字符序列09，解析后是9；0只有一位，直接返回0。结果不超过n，所以在题目范围内不会超过int上限。

设十进制位数为d，扫描、回退和填充合计O(d)，字符数组的额外空间为O(d)。

5. 怎么验证，而不是只看提交截图？

原来的提交结果也保留：

截图中的耗时排名不能当成稳定性能结论。本轮另外用本地程序验证，且同时运行备份中的原Java代码和上面的整理版，不拿另一套贪心程序互相证明。

验证器先递归枚举题目范围内所有十进制非递减整数：第一位从1到9，之后只能追加不小于前一位的数字，超过上界就停止，并单独加入0。将这些合法数排序后，查询不超过n的最大值作为对照答案。

这是另一种解题方式：直接构造合法数，而不是寻找下降点。它规模大于单次贪心查询，但很适合做独立验证。

再增加三类测试：小范围连续输入、固定种子的随机输入、每个合法数本身及相邻整数。既覆盖普通输入，也专门检查答案切换的边界。

本次使用Amazon Corretto 17.0.12，连续范围为0..100000，随机种子408、随机输入10000组；合法数清单有48620个，并用小范围逐数扫描核对了清单查询的答案。总计255867次输入检查，包含边界组之间的重复，不等于255867个互不相同的输入。

PASS: 255867 cases; original and revised match independent oracle Legal numbers=48620; wrong no-backtracking variant: 332 -> 329

还故意删掉回退步骤，检查测试能否抓到332 -> 329这个错误。验证器如果连已知错误都检不出，“全绿”也没什么说服力。

有限测试不是正确性证明，上面的贪心推导仍然必要。测试负责发现实现与边界错误，推导负责说明为什么不是只对样例正确。