C++ में मोनोटोन बढ़ते अंक

मान लीजिए कि हमारे पास एक गैर-ऋणात्मक पूर्णांक N है, तो हमें मोनोटोन बढ़ते अंकों के साथ N से कम या उसके बराबर सबसे बड़ी संख्या ज्ञात करनी होगी। हम जानते हैं कि एक पूर्णांक में मोनोटोन बढ़ते अंक होते हैं यदि और केवल यदि आसन्न अंकों की प्रत्येक जोड़ी 'x और y' x <=y को संतुष्ट करती है।) तो यदि इनपुट 332 की तरह है, तो परिणाम 299 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• s :=N स्ट्रिंग के रूप में, i :=1, n :=s का आकार
• जबकि मैं =s[i – 1]
  • मैं 1 से बढ़ाएँ
• अगर मैं
• जबकि मैं> 0 और s[i – 1]> s[i], तब
  • i 1 से घटाएं
  • s[i] को 1 से घटाएं

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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));
}

इनपुट

332

आउटपुट

299