ধরুন আমাদের একটি অ-ঋণাত্মক পূর্ণসংখ্যা আছে যা একটি স্ট্রিং হিসাবে উপস্থাপিত হয়, আমাদের সংখ্যা থেকে k সংখ্যাগুলি সরিয়ে ফেলতে হবে যাতে নতুন সংখ্যাটি সম্ভাব্য সবচেয়ে ছোট হয়। তাই ইনপুট যদি হয় “1432219” এবং k =3, তাহলে ফলাফল হবে “1219”।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি স্ট্যাক st সংজ্ঞায়িত করুন, একটি খালি স্ট্রিং ret তৈরি করুন
-
n :=সংখ্যার আকার
-
0 থেকে n – 1
রেঞ্জের i জন্য-
যখন k অ শূন্য এবং স্ট্যাক খালি নয় এবং স্ট্যাকের উপরে> num[i>
-
স্ট্যাক থেকে মুছুন এবং k 1 কমিয়ে দিন
-
-
st
-এ num[i] ঢোকান
-
-
যখন k 0 নয়, স্ট্যাক থেকে উপাদান মুছুন
-
স্ট্যাক খালি না থাকা অবস্থায়
-
ret :=ret + স্ট্যাকের শীর্ষ, স্ট্যাক থেকে উপাদান মুছুন
-
-
এখন রেট স্ট্রিং বিপরীত করুন
-
উত্তর :=একটি খালি স্ট্রিং, এবং i :=0
-
যখন i
নয় -
i 1 দ্বারা বাড়ান
-
-
i
এর জন্য -
ans :=ans + ret[i]
-
-
ret :=উত্তর
-
ret এর আকার 0 হলে “0” ফেরত দিন, অন্যথায়, ret
উদাহরণ (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"
