C++ में K डिजिट्स हटाना

मान लीजिए हमारे पास एक नॉन-नेगेटिव इंटीजर num है जिसे स्ट्रिंग के रूप में दर्शाया गया है, हमें नंबर से k डिजिट्स हटाने हैं ताकि नया नंबर सबसे छोटा संभव हो। उदाहरण के लिए, अगर इनपुट "1432219" है और k = 3, तो रिजल्ट "1219" होगा।

इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:

• एक स्टैक st डिफाइन करें, एक खाली स्ट्रिंग ret बनाएं

• n := num का साइज

• i को 0 से n-1 तक लूप करें:

  • जब तक k नॉन-जीरो है और स्टैक खाली नहीं है और स्टैक का टॉप > num[i]:

    • स्टैक से डिलीट करें और k को 1 से घटाएं

  • num[i] को st में इंसर्ट करें

• जब तक k 0 नहीं है, स्टैक से एलिमेंट डिलीट करें

• जब तक स्टैक खाली नहीं है:

  • ret := ret + स्टैक का टॉप, स्टैक से एलिमेंट डिलीट करें

• अब ret स्ट्रिंग को रिवर्स करें

• ans := एक खाली स्ट्रिंग, और i := 0

• जब तक i < ret का साइज और ret[i] '0' नहीं है:

  • i को 1 से बढ़ाएं

• i < ret के साइज के लिए:

  • ans := ans + ret[i]

• ret := ans

• अगर ret का साइज 0 है तो "0" लौटाएं, अन्यथा ret

उदाहरण (C++)

बेहतर समझ के लिए निम्न इम्प्लीमेंटेशन देखें:

class Solution {
public:
    string removeKdigits(string num, int k) {
        stack <char> st;
        string ret = "";
        int n = num.size();
        for(int i = 0; i < n; i++){
            while(k && !st.empty() && st.top() > num[i]){
                st.pop();
                k--;
            }
            st.push(num[i]);
        }
        while(k--)st.pop();
        while(!st.empty()){
            ret += st.top();
            st.pop();
        }
        reverse(ret.begin(), ret.end());
        string ans = "";
        int i = 0;
        while(i < ret.size() && ret[i] == '0')i++;
        for(; i < ret.size(); i++)ans += ret[i];
        ret = ans;
        return ret.size() == 0? "0" : ret;
    }
};

इनपुट

"1432219" 3

आउटपुट

"1219"