#data_structures
#algorithm
# What is monotonic stack
is a special variation of the typical data structure stack. as its name shows it contains all features that a normal stack has and its elements are all monotonic decreasing or increasing.
is a stack with its elements ordered monotonically Specifically, it maintains monotonicity by popping elements when a new element e is pushed into the stack.
## When to use monotonic stack
are best suited for problems that require finding the next/previous greater/smaller element in a list of elements.
to explain the original Next Greater Element problem. give you an array, and return an array of equal length. The corresponding index stores the next larger element, if there is a no larger element, store -1. It's not easy to explain clearly in words. Let's take a direct example:
Give you an array [2,1,2,4,3],and you return an array [4,2,4,-1,-1].
You just iterate through the list and push elements into the stack. The top element in the stack right before the new element is pushed into the stack is the next/previous greater/smaller element of the pushed element. The complexity of doing so for each element in the list is linear.
- 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.
## Implementation
python
class MonotonicStack:
def __init__(self):
self.storage = []
def isEmpty(self) -> bool:
return len(self.storage) == 0
def push(self, value):
while not self.isEmpty() and self.storage[-1] < value:
self.storage.pop()
self.storage.append(value)
I am preparing a video tutorial that shows the use this data structure and solving the most common interview problems with it.
say tuned and be family of my channel by subscribing to this channel and also my YouTube channel
#algorithm
# What is monotonic stack
is a special variation of the typical data structure stack. as its name shows it contains all features that a normal stack has and its elements are all monotonic decreasing or increasing.
is a stack with its elements ordered monotonically Specifically, it maintains monotonicity by popping elements when a new element e is pushed into the stack.
## When to use monotonic stack
are best suited for problems that require finding the next/previous greater/smaller element in a list of elements.
to explain the original Next Greater Element problem. give you an array, and return an array of equal length. The corresponding index stores the next larger element, if there is a no larger element, store -1. It's not easy to explain clearly in words. Let's take a direct example:
Give you an array [2,1,2,4,3],and you return an array [4,2,4,-1,-1].
You just iterate through the list and push elements into the stack. The top element in the stack right before the new element is pushed into the stack is the next/previous greater/smaller element of the pushed element. The complexity of doing so for each element in the list is linear.
- 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.
## Implementation
python
class MonotonicStack:
def __init__(self):
self.storage = []
def isEmpty(self) -> bool:
return len(self.storage) == 0
def push(self, value):
while not self.isEmpty() and self.storage[-1] < value:
self.storage.pop()
self.storage.append(value)
I am preparing a video tutorial that shows the use this data structure and solving the most common interview problems with it.
say tuned and be family of my channel by subscribing to this channel and also my YouTube channel