Monotonic stack is a variation of data structure stack and also appeared in many interviews of big and small tech companies.
It contains all features of the normal stack and its elements are all monotonic increasing or decreasing.
When we use Monotonic Stack
Mono-decreasing Stack Before: [5,4,3,1] To push 2, we need to pop smaller (or equal) elements first After: [5,4,3,2]
Monotonic stacks are useful when we have to find the next/previous greater/smaller element in the list of elements.
It is a “range queries in an array” problem
Example Leetcode 316. Remove Duplicate Letters
the monotonic stack can help us to solve the problem, but we actually use a variant of the monotonic stack.
Because the problem requirement is to find the smallest lexicographical order, the characters in the stack should be in the increasing order, the tail of the stack has the smallest value, the top of the stack has the biggest value -> tail
abcd top < tail
dcba top (lexicographical order)
last is used to track where the character last appear, it helps us to determine whether to remove the character at the top of the stack if the character has duplicates after the current index
keyInStack is used to track what the characters in the stack, if the character has been in the stack, we can skip it.
the key idea is how to maintain the monotonic stack (how to remove the top character of the stack).
If the top character of the stack is greater than the current character
c and the top character of the stack has duplicates after the current character
then we can remove it because we have other choices for this character (the top character of the stack) after the current character
c to maintain the monotonic stack.
But we only have one choice of character, we can't remove it.
If the problem asks us to find the biggest lexicographical order, we just maintain the monotonic stack in the decreasing order (the tail of the stack has the biggest value), the rest is the same, then we can get an answer in the biggest lexicographical order.
Time Complexity: O(N), sc: O(1), space of
stack <= 128
class Solution: def removeDuplicateLetters(self, s: str) -> str: stack, last, keyInStack = , [-1] * 128, set() for idx, c in enumerate(s): last[ord(c)] = idx for idx, c in enumerate(s): if c in keyInStack: continue keyInStack.add(c) while len(stack) and stack[-1] > c and last[ord(stack[-1])] > idx: keyInStack.remove(stack.pop()) stack.append(c) return ''.join(stack)
Example Leetcode: 402. Remove K Digits
The monotonic stack can help us to solve the problem.
because the problem requirement is to find the smallest possible integer, so monotonic stack can be maintained in increasing order, ex stack -> tail
when keeping an increasing order for the stack, we only can remove elements from the top of the stack
and we push the element to stack. if the element equals to
'0' and the stack is empty,
it can not be pushed to the stack. (or we can do post-precessing for
'0' s on the left side)
k not equals to
0 which means there are some digits of
num in increasing order, ex. num =
123456, k =
3, stack =
because the elements in the stacks are in increasing order, we just remove
k elements from the top of the stack if
k not equals to
finally, if the stack is empty return
'0', or return the string after concatenating.
Time Complexity: O(N), sc: O(N)
class Solution: def removeKdigits(self, num: str, k: int) -> str: stack =  for val in num: while stack and k > 0 and val < stack[-1]: stack.pop() k-=1 stack.append(val) stack = stack[:len(stack)-k] res = "".join(stack) return str(int(res)) if res else "0"
Thank you for reading this blog subscribe for more.