Description Link to heading
brief Link to heading
Monotone stack is a stack whose elements(from top to bottom) are (strictly) monotonically increasing or decreasing.
Monotone increasing stack: the element which is smaller than the element in the top can be pushed into stack, else we will pop the element in the top, until the stack is empty or the element is smaller than the element in the top, then we push the element into the stack. This data structure is usually used for problems to find first element that is larger than certain element.
Monotone decreasing stack: is the opposite of a monotonically increasing stack, used for problems to find first element that is smaller than certain element.
how to judge Link to heading
Monotonically increasing/decreasing stacks are generally determined by the order in which they exit the stack
the sentry tips Link to heading
Sometimes, if all the elements in the array is needed, that is: all the elements in the stack will be popped. It’s very likely that the border will not be passed because it is not considered. So we can use the sentinel method.
For example, adding a -1 at the end of {1, 3, 4, 5, 2, 9, 6} as a sentinel, it becomes {1, 3, 4, 5, 2, 9, 6, -1}, a trick that simplifies the code logic.