หาตัวเลขที่มีหลักเพิ่มขึ้นเรื่อยๆ น้อยที่สุดใน C++

ให้จำนวนเต็มบวก N หาตัวเลขที่มากที่สุดซึ่งน้อยกว่าหรือเท่ากับ N และมีหลักตัวเลขเรียงเพิ่มขึ้นเรื่อยๆ (แต่ละคู่ของหลักที่อยู่ติดกัน x และ y ต้องมี x ≤ y) ตัวอย่างเช่น หาก input = 332 ผลลัพธ์จะเป็น 299

วิธีแก้ปัญหา

1. แปลง N เป็นสตริง s, กำหนด i = 1, n = ความยาวของ s
2. วนลูป while i < n และ s[i] ≥ s[i-1]: เพิ่ม i ขึ้น 1
3. หาก i < n:
   • วนลูป while i > 0 และ s[i-1] > s[i]:
     • ลด i ลง 1
     • ลดค่า s[i] ลง 1
4. สำหรับ j จาก i+1 ถึง n-1: กำหนด s[j] = '9'
5. คืนค่า s เป็นตัวเลข

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

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string s = to_string(N);
        int i = 1;
        int n = s.size();
        while (i < n && s[i] >= s[i - 1]) i++;
        if (i < n)
            while (i > 0 && s[i - 1] > s[i]) {
                i--;
                s[i]--;
            }
        for (int j = i + 1; j < n; j++) s[j] = '9';
        return stoi(s);
    }
};

int main() {
    Solution ob;
    cout << ob.monotoneIncreasingDigits(332);
    return 0;
}

Input

332

Output

299