题目重点：从 132→141 推导最小严格更大回文整数，处理已有回文、连续 9、位数增长与超长十进制输入。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入采用无前导零的非负十进制字符串；用字符串支持超过固定宽度整数的值。
- 返回严格大于输入的最小十进制回文数；即便输入自身已是回文，也不能原样返回。
- 负数、含前导零与非数字字符题目未定义，训练实现拒绝。
解题路线
- 先把左半边镜像到右半边，得到与原数同前缀的回文候选。若它已经严格大于输入，它就是该左半前缀下的最小可行结果。
- 否则将中间位向左做十进制 +1 进位：奇数长度从中心位起，偶数长度从左中心位起；再把更新后的左半镜像到右半。
- 若进位越过最高位，输入只能是全 9 型的情况，答案为 1、若干个 0、1，比原长度多一位。
- 严格最小性来自回文数由左半/中心决定，按该前缀的数值顺序递增；若当前镜像不够大，下一前缀加 1 是最近可行者。
手动走一遍
132 镜像得 131，不够大；中心 3 加 1，再镜像得到 141。1291 镜像为 1221，不够大；左半 12 递增到 13 得 1331。99 进位溢出，得到 101。输入 121 本身回文，下一答案是 131。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def next_palindrome(value: str) -> str:
"""Smallest decimal palindrome strictly greater than a nonnegative integer."""
if not value or not value.isdecimal() or (len(value) > 1 and value[0] == "0"):
raise ValueError("expected canonical nonnegative decimal integer")
digits = list(value)
n = len(digits)
mirrored = digits[:]
for i in range(n // 2):
mirrored[n - i - 1] = mirrored[i]
if "".join(mirrored) > value:
return "".join(mirrored)
i = (n - 1) // 2
carry = 1
while i >= 0 and carry:
digit = ord(mirrored[i]) - 48 + carry
mirrored[i] = str(digit % 10)
carry = digit // 10
i -= 1
if carry:
return "1" + "0" * (n - 1) + "1"
for i in range(n // 2):
mirrored[n - i - 1] = mirrored[i]
return "".join(mirrored)
if __name__ == "__main__":
assert next_palindrome("132") == "141"
复杂度
字符串长度为 d，镜像、比较、进位各最多扫 O(d)，总 O(d) 时间与 O(d) 额外空间。返回值也占 O(d) 字符。
易错点与追问
容易失分的边界
- 判断原数是回文后直接返回，违反‘下一个更大’。
- 只把左半复制到右半，132 会得到更小的 131。
- 连续 9 进位时未处理位数增长，例如 99→101。
- 把十进制大数强转固定宽度整型造成溢出。
- 偶数长度把右中心位当作需要进位的位，破坏镜像规则。
继续深挖
- 若要求下一个更小回文数，借位与去前导零如何处理？
- 输入有小数点、负号时回文定义是什么？
- 如果只能原地修改字符数组，额外空间能降到多少？
