Introduction to monotonic stack that everyone can understand

Monotonic stack is a stack with the guarantee of monotonicity for stack elements, which is more strictly limited than a normal stack. It requires that every element pushed onto the stack must be sorted (if the new element pushed does not meet the requirement, the previous elements will be popped out of the stack until the requirement is met before pushing the new element), forming a monotonic increasing or decreasing stack.

Monotonic stack is a relatively simple data structure. Compared with monotonic queue, it only performs push and pop operations on one end.

This article mainly introduces the concept and basic operations of monotonic stack with a typical example, focusing on explaining the intuition behind it.

Leetcode 739. Daily Temperatures

Description of the problem:

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.

Example 1:

Input: temperatures = [73,74,75,71,69,72,76,73] 

Output: [1,1,4,2,1,1,0,0]

This problem is the most typical application of monotonic stack: finding the first element on the left or right sides of a certain element that is greater than (or less than) it.

The first idea is to search sequentially for each temperature value towards the back until a higher value is found. This is the easiest method to think of. The code is as follows:

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        for i in range(len(temperatures)):
            for j in range(i+1, len(temperatures)):
                if temperatures[j] > temperatures[i]:
                    res[i] = j - i
                    break

        return res

Obviously, the time complexity of this solution is O(n²), so we need to find a faster method to reduce the number of iterations.

How can we reduce the number of iterations?

As shown in the figure below, starting from 75, the area inside the box will be repeatedly traversed. If we can reduce the number of traversals in this area, we can improve the overall computational efficiency.

Insight

Generally, significant reduction in time complexity requires some insight.

We can observe the following phenomenon: a number cannot be the next maximum value of every number in a monotonically increasing subsequence of length greater than 2 in the original array.

This is obvious: [73,74] form a monotonically increasing subsequence in example 1, and 75 can only be the next maximum value of 74, not 73.

Thus, we have this insight: a number can only be the next maximum value of each number in the original array’s monotonically non-increasing subsequence.

For example, in example 1, array is[73,74,75,71,69,72,76,73]:

• 74 is the next largest value after 73, and 73 is a monotonic non-increasing subsequence of the original array.
• 72 is the next largest value after 71 and 69, and 71 and 69 form a monotonic non-increasing subsequence of the original array.

This inspires us to maintain a monotonic non-increasing sequence by enumerating from 1 to n , and checking if the value at the end of the sequence(represented by top) is less than the current value(represented by cur).

• If top <= cur, the current position is the answer, update the answer and delete it.
• If top > cur, add it to the sequence, because the current position can no longer be the answer to the previous numbers.

We find that the operation we are doing is similar to a stack, so we call the above algorithm a monotonic stack, and we are maintaining a monotonic non-increasing stack.

Notice that each element is pushed and popped from the stack at most once, so the time complexity is O(n).

Pseudo-code for inserting a new element is as follows:

inset_mono_stack(cur)
{
    while (!stack.empty() and stack.top() < cur)
        stack.pop()
    stack.push(x)
}

With the above ideas, the code for LeetCode 739 can be written as follows:

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        st = []
        res = [0] * len(temperatures)
        for i in range(len(temperatures)):
            while st and temperatures[st[-1]] < temperatures[i]:
                res[st[-1]] = i - st[-1]
                st.pop()
            st.append(i)
        
        return res

The impact of each element in an array on a monotonic stack is shown in the following diagram, it can be seen that the stack is monotonically non-increasing from the bottom to the top:

It is worth mentioning that we found two elements, 73 and 76, still left in the monotonic stack without the next maximum value. This is resolved by setting default values directly when applying for the res array.

However, for some problems where all elements of the array are used, that is, all elements in the stack need to be popped out, it is likely that the solution cannot pass because the boundary is not considered. Therefore, we can use the sentinel method by adding a sentinel at the end of the original sequence, which will be explained in detail when discussing typical problems of monotonic stack in the future.

Conclusion

In this article, we have explored the intuition behind the monotonic stack algorithm.

We have seen that the monotonic stack is a useful data structure for finding the next greater or next smaller element for every element in an array.

We have also seen how the algorithm works and how it can be applied to solve a coding problem.

Finally, if there are any omissions or errors in this article, please kindly advise me. Thank you.

References

https://leetcode.com/problems/daily-temperatures/