What is Monotonic Stack?

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

• For greater problems, use a monotonically increasing stack (from top to bottom).
• For smaller problems, use a monotonically decreasing stack (from top to bottom).
• For next problems, backwardly iterate through the list and push elements into the stack.
• For previous problems, forwardly iterate through the list.
• For problems with a circular list, iterate through the list twice.

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)

array 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 idx

hash table 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 c,
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 keyInStack, 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 12345 top

when keeping an increasing order for the stack, we only can remove elements from the top of the stack k times.

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)

after iterating num, if k not equals to 0 which means there are some digits of num in increasing order, ex. num = 123456, k = 3, stack = 1,2,3,4,5,6

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 0

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.