โปรแกรมหาตัวเลขไม่เกิน n ที่หลักต่างๆ ไม่ลดลงใน Python

สมมติว่ามีตัวเลข n ต้องการหาตัวเลขที่มากที่สุดแต่น้อยกว่าหรือเท่า n โดยที่ทุกหลักเป็น non-decreasing (ไม่ลดลงจากซ้ายไปขวา)

ตัวอย่าง: n = 221 ผลลัพธ์คือ 199

ขั้นตอนการแก้ปัญหา

1. แปลง n เป็นรายการหลัก digits
2. bound = None
3. วนลูปจากหลักท้ายไปหน้า (i = len(digits)-1 ถึง 1):
   • ถ้า digits[i] < digits[i-1]:
     • bound = i
     • digits[i-1] -= 1
4. ถ้า bound ไม่เป็น None:
   • ตั้งค่า digits[i] = 9 สำหรับ i จาก bound ถึงท้าย
5. รวมหลักกลับเป็นตัวเลขและคืนค่า

ตัวอย่างโค้ด

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