July 5, 2022

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.