Pythonで各桁が非減少となるn以下の最大の数を求めるプログラム

問題の概要

ある整数 n が与えられたとき、「すべての桁が非減少（左から右へ見て、どの桁もひとつ前の桁以上である）」という条件を満たす、n 以下の最大の数を求めます。

たとえば入力が n = 221 のとき、出力は 199 になります。221 は「2 → 1」という減少を含むため条件を満たさず、条件を満たす数の中で最も大きいものが 199 だからです。

解法のアプローチ

この問題は、次の手順で解くことができます。

• n の各桁をリスト digits として取り出します。
• 減少が発生した位置を記録するための変数 bound を用意します。
• 右端の桁から左へ向かって走査します。
• digits[i] < digits[i - 1]（桁が減少している）場合は、その位置 i を bound に記録し、ひとつ左の桁 digits[i - 1] を 1 減らします。
• bound が設定されている場合は、bound 以降のすべての桁を 9 に置き換えます。
• 最後に、各桁を連結して数値に戻し、結果として返します。

実装例（Python コード）

理解を深めるために、以下の実装例を見てみましょう。

class Solution:
    def solve(self, n):
        digits = [int(x) for x in str(n)]
        bound = None
        for i in range(len(digits) - 1, 0, -1):
            if digits[i] < digits[i - 1]:
                bound = i
                digits[i - 1] -= 1
            if bound:
                for i in range(bound, len(digits)):
                    digits[i] = 9
        return int("".join(map(str, digits)))

ob = Solution()
n = 221
print(ob.solve(n))

入力

221

出力

199

アルゴリズムのポイント

このアルゴリズムの核心は、「減少が起きた桁の左隣を 1 減らし、それ以降（右側）をすべて 9 で埋める」という操作にあります。こうすることで、n を超えない範囲で各桁が単調に増加（または一致）する最大の数を作れます。

例として n = 221 の動作を追うと、次のようになります。

1. 初期状態：[2, 2, 1]
2. i = 2：digits[2] = 1 < digits[1] = 2 なので、bound = 2 とし、digits[1] を 1 減らして [2, 1, 1] にします。
3. i = 1：digits[1] = 1 < digits[0] = 2 なので、bound = 1 とし、digits[0] を 1 減らして [1, 1, 1] にします。
4. bound = 1 以降の桁をすべて 9 にして [1, 9, 9]、つまり 199 が得られます。

計算量

桁数を d とすると、走査と 9 への置き換えはそれぞれ 1 回ずつ行うだけなので、時間計算量は O(d)、空間計算量も O(d) となります。桁数が非常に大きな n に対しても効率的に動作します。

補足：実装上の注意点

サンプルコードでは bound の判定に if bound: を使っています。ループが i = 1 までしか回らないため bound が 0 になることはなく、この書き方でも正しく動作します。ただし、より安全で意図が明確なコードにするなら、if bound is not None: と書くのがおすすめです。