เสียงเดียวที่เพิ่มขึ้นตัวเลขใน C ++

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

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

s :=N เป็นสตริง i :=1, n :=ขนาดของ s
ในขณะที่ i
=s[i – 1]
- เพิ่ม i ขึ้น 1
ถ้าฉัน
ในขณะที่ i> 0 และ s[i – 1]> s[i] แล้ว
- ลดลง 1
- ลด s[i] ลง 1

สำหรับ j ในช่วง i + 1 ถึง n

s[j] :='9'

ส่งคืนเป็นตัวเลข

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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);
   }
};
main(){
   Solution ob;
   cout << (ob.monotoneIncreasingDigits(332));
}