Chương trình tìm số không lớn hơn n có các chữ số không giảm trong Python

Mô tả bài toán

Cho số nguyên n. Tìm số lớn nhất ≤ n sao cho các chữ số của nó không giảm (tức mỗi chữ số ≤ chữ số bên phải).

Ví dụ: n = 221 → đầu ra 199.

Giải thuật

1. Chuyển n thành mảng chữ số digits.
2. Khởi tạo bound = None.
3. Duyệt từ phải sang trái (i từ len(digits)-1 xuống 1):
   • Nếu digits[i] < digits[i-1]: đặt bound = i, giảm digits[i-1] đi 1.
4. Nếu bound không phải None: đặt tất cả chữ số từ bound đến cuối thành 9.
5. Ghép các chữ số thành số nguyên và trả về.

Ví dụ mã 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 is not None:
            for i in range(bound, len(digits)):
                digits[i] = 9
        return int("".join(map(str, digits)))

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

Đầu vào

221

Đầu ra

199