मान लीजिए कि हमारे पास एक गैर-ऋणात्मक पूर्णांक संख्या है जिसे एक स्ट्रिंग के रूप में दर्शाया गया है, हमें संख्या से k अंक निकालना होगा ताकि नई संख्या सबसे छोटी संभव हो। तो अगर इनपुट “1432219” और k =3 जैसा है, तो परिणाम “1219” होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
स्टैक सेंट को परिभाषित करें, एक खाली स्ट्रिंग रिट बनाएं
-
n :=संख्या का आकार
-
मेरे लिए 0 से n - 1 की सीमा में
-
जबकि k शून्य नहीं है और स्टैक खाली नहीं है और स्टैक के शीर्ष पर है> num[i]
-
स्टैक से हटाएं और k को 1 से घटाएं
-
-
num[i] सेंट में डालें
-
-
जबकि k 0 नहीं है, स्टैक से तत्व हटाएं
-
जबकि ढेर खाली नहीं है
-
रिट:=रिट + स्टैक के ऊपर, स्टैक से तत्व हटाएं
-
-
अब रिट स्ट्रिंग को उल्टा करें
-
उत्तर:=एक खाली स्ट्रिंग, और मैं:=0
-
जबकि i <रिट और रिट का आकार [i] '0' नहीं है
-
1 से बढ़ाएँ
-
-
मैं के लिए <रिट का आकार
-
उत्तर:=उत्तर + रिट[i]
-
-
रिट:=उत्तर
-
यदि रिट का आकार 0 है, तो "0" लौटाएं, अन्यथा, रिट करें
उदाहरण (C++)
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
class Solution {
public:
string removeKdigits(string num, int k) {
stack 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"