NeetCode #360LC-402MediumStack
← Back to All Problems#360 · #402 · Remove K Digits(移掉 K 位数字)
📌 Problem Statement & Constraints
Given a non-negative integer as a string
num and an integer k, remove k digits so that the remaining number is the smallest possible, preserving the relative order of the remaining digits. Return the result as a string with no leading zeros (use "0" if the result is empty). Constraints: 1 <= k <= num.length <= 10^5.💡 Core Algorithmic Approaches
- This is the classic "remove digits to minimise" greedy, solved with a monotonically increasing stack.
- For each digit, while the stack top is greater than the current digit and removals remain, pop it -- a larger leading digit is always worse.
- Push the current digit. If removals remain after the scan, they must come off the end (the number is already non-decreasing).
- Finally strip leading zeros; an all-zero result becomes
"0".
💻 Benchmark Python3 Implementation
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
st = []
for d in num:
# pop larger leading digits while we still have removals
while k and st and st[-1] > d:
st.pop()
k -= 1
st.append(d)
if k: # number is already non-decreasing
st = st[:-k] # remove from the end
res = "".join(st).lstrip("0")
return res if res else "0"⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each digit is pushed once and popped at most once.
💾 Space Complexity
O(n) for the stack.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the leftover
k: if the digits are already non-decreasing, the removals must come from the end. - Using
>=in the pop condition: removing equal digits is never beneficial, and it can produce a worse result for the same removal count. Use strict>. - Forgetting to strip leading zeros:
"10200"withk = 1gives"200", but"100"withk = 1gives"00", which must become"0". - Returning an empty string: the contract requires
"0".
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.