单调递增的数字

n 可能很大(到 10 位数),一个个往下试要试几亿次,必然超时。得找规律。

把「左位减 1、右边全填 9」记牢。减 1 是为了变小到 ≤n,填 9 是为了在变小的前提下尽量大。下面一帧帧演给你看。

起步 · n = 332：把 332 拆成三位数字 [3, 3, 2] 排成一排,下标 0、1、2。我们要从最右边的相邻对开始,一对对往左查「有没有下坡」。

看最右一对 · 下标 1 与 2：指针落在最右位 下标 2,看它和左边邻居 下标 1 这一对。问:左边 3 是不是大于右边 2?

3 > 2 · 是下坡!：3 > 2,是下坡!按规律:左边这位 3 减 1 变成 2(数字真的变了),并记下 mark=2——意思是「从下标 2 开始往后都要填 9」。

继续往左 · 下标 0 与 1：指针往左挪到 下标 1,看它和更左的 下标 0 这一对。注意此刻 s[1] 已经是刚减过的 2。再问:3 > 2 吗?

又是 3 > 2 · 再下坡!：又是下坡!s[0] 由 3 减为 2,mark 更新成 1(因为减 1 发生在更左边,填 9 的起点也要跟着左移)。数字现在是 [2, 2, 2]。

到最左了 · 扫描结束：指针到了最左位,再没有「左边邻居」可比,比较阶段结束。现在数字是 [2, 2, 2],记着的 mark = 1。下一步:从 mark 开始填 9。

填 9 · 下标 1 → 9：进入填 9 阶段:从 mark=1 这位开始,下标 1 改成 9。为什么填 9?因为前面减了 1 已经保证比 n 小,后面就该尽量大,9 最大。

填 9 · 下标 2 → 9：再把 下标 2 也改成 9。填到末尾,数字变成 [2, 9, 9],也就是 299——正是答案!

332 → 299 ✓：检验:2 ≤ 9 ≤ 9 确实单调递增,且不超过 332。一次从右往左的扫描就拿到了答案 299。

再演一例 · n = 1234：换个数 1234 看看「本来就递增」会怎样。同样从最右一对开始往左查下坡。

3 < 4 · 不是下坡：最右一对 3 和 4:3 < 4,不是下坡,什么都不改,指针往左挪。

2 < 3 · 不是下坡：再往左一对 2 和 3:还是 2 < 3,不是下坡,继续左移。

1 < 2 · 不是下坡：最左一对 1 和 2:依旧 1 < 2。全程没找到下坡,mark 始终为「无」。

1234 → 1234 ✓：既然没下坡,就不减也不填,1234 本身已经单调递增,直接返回 1234。

易错例 · n = 10：看一个易错例 10:最右一对 1 和 0,1 > 0 是下坡。左位要减 1。

10 · 减 1 + 填 9：s[0] 减成 0,mark=1 让 s[1] 填 9,字符串变成 "09"。注意最高位成了 前导 0!

10 → 9 ✓：把 "09" 转回整数,前导 0 自动消失(下标 0 那位被丢弃,变灰),得到 9。所以代码最后用「转整数」一步天然处理了前导 0,不用特判。

再演一例 · n = 100：再看 100。最右一对是 0 和 0,相等不算下坡(要求是「左 > 右」),不改,指针左移。

100 · 下标 0 与 1：往左一对 1 和 0:1 > 0 是下坡!左位要减 1,并记 mark。

100 · 减 1 + 记 mark：s[0] 由 1 减成 0,记下 mark=1。数字暂时是 [0, 0, 0]。

100 · 从 mark 填 9：从 mark=1 起把下标 1、2 都填 9,得到 "099",转整数去掉前导 0 → 99。

如果从左往右,改了前面的位,后面已经检查过的就可能又被破坏、来不及补救。从右往左保证每次改动只影响「更左、还没查的」位,一遍扫描就够。

边界三连：先想前导 0(10)、已递增(1234)、连锁减 1(332)三种,代码就稳了。

面试追问：把「贪心为何对」「为何从右往左」「前导 0 怎么处理」讲清楚,是这题面试的得分点。