Remove K Digits — Greedy Monotonic Stack
Sanjeev SharmaAdvertisement
Problem
Remove k digits from num to form the smallest possible number.
Approach — Monotonic Stack
Maintain increasing stack. For each digit, pop from stack if stack top is larger AND we still have removals left. Remaining pops from end.
Time: O(n) | Space: O(n)
Solutions
Python
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
stack=[]
for d in num:
while k and stack and stack[-1]>d:
stack.pop(); k-=1
stack.append(d)
stack=stack[:-k] if k else stack
return ''.join(stack).lstrip('0') or '0'
C++
class Solution {
public:
string removeKdigits(string num, int k){
string st;
for(char d:num){
while(k&&!st.empty()&&st.back()>d){st.pop_back();k--;}
st+=d;
}
while(k--) st.pop_back();
int i=0; while(i<st.size()-1&&st[i]=='0') i++;
return st.substr(i);
}
};
Complexity
- Time: O(n) | Space: O(n)
Advertisement
