Space
Open
From Fieldwork
Scales
Archive
Eventually, all monotonic stack problems have a panacea which consists of two questions: "What happens if it's ascending? What happens if it's descending?"
But it's not just about the two extremes. Sure, they illuminate the behavioural boundaries, but it's also what we're doing at every step of the process. In fact, it's all we're doing. It's the only two operations that the algorithm performs, over and over. The switch flips.
It is a mechanism to enforce a specific slope by eagerly destroying anything that violates it.
Instead of looking ahead to find the smallest, we can look at the neighbour, and iterate through the string only once. We use a stack to keep track of the digits we represent "keeping."
The state of the world when the loop finishes is that the stack is in ascending (non-decreasing) order.
If the loop finishes and we still have k > 0, it means we never found a "peak" to chop off. We can't promote the second number, or anything at all. We have to start chopping the back. That's the fat to trim.
There's a really funny way of seeing this problem as a really intense NIMBY Mayor where you're given k Demolition Permits to destroy tall buildings. We want a really low building, and we want to have a view, and sun.
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
stack = []
for digit in num:
# While we have k to spend, the stack isn't empty,
# and the previous digit is bigger than the current one:
while k > 0 and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# Edge Case 2: If the numbers were already ascending (e.g. '12345', k=2),
# we might still have k left to remove. Remove from the end.
if k > 0:
stack = stack[:-k]
# Join the stack to form the string
result = ''.join(stack)
# Edge case 3: remove leading zeroes
result = result.lstrip('0')
# Edge case 4: If the string is empty (we removed everything), return '0'
return result if result else '0'Practice bench
A private scratchpad for this reading. Nothing is sent or scored.
What is still unclear, or what would change the explanation?
Saved on this device · one draft per mode