Algorithms for Interview 2: Monotonic Stack
Introduction
Monotonic Stack is a special variation of the typical data structure Stack and appeared in many interview questions.
As its name shows, monotonic stack contains all features that a normal stack has and its elements are all monotonic decreasing or increasing.
When to Use Monotonic Stack
Monotonic Stack is the best time complexity solution for many “range queries in an array” problems. Because every element in the array could only enter the monotonic stack once, the time complexity is O(N). (N represents the length of the array).
For every “range query” problem, it could be sure to maintain a range using a normal array/list. However, we will do many repetitive operations to get information from every range. The time complexity is very high and the solution is always not good enough to pass an interview.
Using monotonic stack to maintain a range can save lots of time. Because it only updates information within the range based on new adding elements and avoids repetitive operations of existing elements. To be more precisely, the monotonic stack helps us maintain maximum and and minimum elements in the range and keeps the order of elements in the range. Therefore, we don’t need to compare elements one by one…
