Monotonic Stack Code Template

A stack is a simple data structure that follows the Last In, First Out (LIFO) principle, suitable for certain problems like function call stacks. A monotonic stack is essentially a stack that uses clever logic to keep its elements sorted (either monotonically increasing or decreasing) after each new element is pushed.

Sounds a bit like a heap? No, monotonic stacks are not widely used and are mainly for specific problems, such as finding the "next greater element" or the "previous smaller element." This article explains the monotonic stack algorithm template to solve "next greater element" problems and discusses strategies for handling "circular arrays." Other variations and classic problems will be covered in the next article Monotonic Stack Variations and Classic Exercises.

Monotonic Stack Template

Here's a problem for you: Given an array nums, return an array of the same length where each index stores the next greater element. If there is no greater element, store -1. The function signature is as follows:

int[] calculateGreaterElement(int[] nums);

vector<int> calculateGreaterElement(vector<int>& nums);

def calculateGreaterElement(nums: List[int])

func calculateGreaterElement(nums []int) []int

var calculateGreaterElement = function(nums) {}

For example, given an array nums = [2,1,2,4,3], you should return the array [4,2,4,-1,-1]. This is because the first 2 is followed by 4, which is greater than 2; 1 is followed by 2, which is greater than 1; the second 2 is followed by 4, which is greater than 2; after 4, there is no number greater than 4, so we fill in -1; after 3, there is no number greater than 3, so we fill in -1.

The brute-force solution to this problem is straightforward: for each element, scan the subsequent elements to find the first greater element. However, the time complexity of the brute-force solution is $O(n^2)$.

This problem can be abstracted as follows: imagine the elements of the array as people standing in a line, with their values representing their heights. These people are facing you, standing in a row. How do you find the next greater element for the element "2"? It's simple—if you can see the element "2", the first visible person behind it is the next greater element because shorter elements are blocked by "2". The first one to appear is the answer.

This scenario is easy to understand, right? With this abstract scenario in mind, let's look at the code.

int[] calculateGreaterElement(int[] nums) {
    int n = nums.length;
    // array to store the answers
    int[] res = new int[n];
    Stack<Integer> s = new Stack<>(); 
    // push elements into the stack from the end
    for (int i = n - 1; i >= 0; i--) {
        // compare the heights
        while (!s.isEmpty() && s.peek() <= nums[i]) {
            // shorter ones step aside, they're blocked anyway...
            s.pop();
        }
        // the greater element behind nums[i]
        res[i] = s.isEmpty() ? -1 : s.peek();
        s.push(nums[i]);
    }
    return res;
}

vector<int> calculateGreaterElement(vector<int>& nums) {
    int n = nums.size();
    // array to store the answer
    vector<int> res(n);
    stack<int> s; 
    // push elements into the stack in reverse order
    for (int i = n - 1; i >= 0; i--) {
        // compare the heights
        while (!s.empty() && s.top() <= nums[i]) {
            // shorter ones step aside, they're blocked anyway...
            s.pop();
        }
        // the greater element behind nums[i]
        res[i] = s.empty() ? -1 : s.top();
        s.push(nums[i]);
    }
    return res;
}

def calculateGreaterElement(nums):
    n = len(nums)
    # array to store the answers
    res = [0]*n
    s = []
    # push elements into the stack backwards
    for i in range(n-1, -1, -1):
        # compare the heights
        while s and s[-1] <= nums[i]:
            # shorter ones step aside, they're blocked anyway...
            s.pop()
        # the greater element behind nums[i]
        res[i] = -1 if not s else s[-1]
        s.append(nums[i])
    return res

func calculateGreaterElement(nums []int) []int {
    n := len(nums)
    // array to store the answers
    res := make([]int, n)
    s := make([]int, 0)
    // push elements into the stack from the end
    for i := n - 1; i >= 0; i-- {
        // compare the heights
        for len(s) != 0 && s[len(s) - 1] <= nums[i] {
            // remove shorter ones, they're blocked anyway...
            s = s[:len(s)-1]
        }
        // the greater element behind nums[i]
        if len(s) == 0 {
            res[i] = -1
        } else {
            res[i] = s[len(s) - 1]
        }
        s = append(s, nums[i])
    }
    return res
}

var calculateGreaterElement = function(nums) {
    var n = nums.length;
    // array to store the answers
    var res = new Array(n);
    var s = []; 
    // putting elements into the stack in reverse order
    for (var i = n - 1; i >= 0; i--) {
        // comparing heights
        while (s.length != 0 && s[s.length-1] <= nums[i]) {
            // shorter ones step aside, they're blocked anyway...
            s.pop();
        }
        // the greater element behind nums[i]
        res[i] = s.length == 0 ? -1 : s[s.length-1];
        s.push(nums[i]);
    }
    return res;
}

This is the template for solving problems using a monotonic queue. The for loop scans elements from back to front because we utilize a stack structure, pushing elements in reverse order, which results in popping them in the correct order. The while loop removes elements between two "taller" elements since their existence is meaningless; a "taller" element in front makes them impossible to be the next greater element for any subsequent incoming elements.

The time complexity of this algorithm is not immediately intuitive. If you see a for loop nested with a while loop, you might think the complexity is $O(n^2)$. However, the actual complexity of this algorithm is $O(n)$.

To analyze its time complexity, consider the whole process: there are n elements in total, and each element is pushed onto the stack once and may be popped from the stack at most once, with no redundant operations. Therefore, the total computation is proportional to the number of elements n, which gives it a complexity of $O(n)$.

Problem Variations

The code implementation of a monotonic stack is relatively straightforward. Let’s look at some specific problems.

496. Next Greater Element I

Let's start with a simple variation, LeetCode Problem 496 "Next Greater Element I":

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

In this problem, you are given two arrays, nums1 and nums2, and you need to find the next greater element of each element in nums1 within nums2. The function signature is as follows:

int[] nextGreaterElement(int[] nums1, int[] nums2)

vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2)

from typing import List

def nextGreaterElement(nums1: List[int], nums2: List[int]) -> List[int]:

func nextGreaterElement(nums1 []int, nums2 []int) []int

var nextGreaterElement = function(nums1, nums2) {}

In fact, we can solve this problem by modifying our previous code. Since the problem states that nums1 is a subset of nums2, we first calculate the next greater element for each element in nums2 and store it in a mapping. Then, we simply look up the elements of nums1 in this mapping:

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // record the next greater element for each element in nums2
        int[] greater = calculateGreaterElement(nums2);
        // convert to a mapping: element x -> x's next greater element
        HashMap<Integer, Integer> greaterMap = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            greaterMap.put(nums2[i], greater[i]);
        }
        // nums1 is a subset of nums2, so we can get the result based on greaterMap
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = greaterMap.get(nums1[i]);
        }
        return res;
    }

    int[] calculateGreaterElement(int[] nums) {
        // see above
    }
}

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        // Record the next greater element for each element in nums2
        vector<int> greater = calculateGreaterElement(nums2);
        // Convert to a mapping: element x -> x's next greater element
        unordered_map<int, int> greaterMap;
        for (int i = 0; i < nums2.size(); i++) {
            greaterMap[nums2[i]] = greater[i];
        }
        // nums1 is a subset of nums2, so we can get the result based on greaterMap
        vector<int> res(nums1.size());
        for (int i = 0; i < nums1.size(); i++) {
            res[i] = greaterMap[nums1[i]];
        }
        return res;
    }

    vector<int> calculateGreaterElement(vector<int>& nums) {
        // See above
    }
};

class Solution:
    def nextGreaterElement(self, nums1, nums2):
        # Record the next greater element for each element in nums2
        greater = self.calculateGreaterElement(nums2)
        # Convert to a mapping: element x -> x's next greater element
        greaterMap = {}
        for i in range(len(nums2)):
            greaterMap[nums2[i]] = greater[i]
        # nums1 is a subset of nums2, so we can get the result based on greaterMap
        res = [0] * len(nums1)
        for i in range(len(nums1)):
            res[i] = greaterMap[nums1[i]]
        return res

    def calculateGreaterElement(self, nums):
        # See above
        pass

func nextGreaterElement(nums1 []int, nums2 []int) []int {
    // Record the next greater element for each element in nums2
    greater := calculateGreaterElement(nums2)
    // Convert to a mapping: element x -> x's next greater element
    greaterMap := make(map[int]int)
    for i := 0; i < len(nums2); i++ {
        greaterMap[nums2[i]] = greater[i]
    }
    // nums1 is a subset of nums2, so we can get the result based on greaterMap
    res := make([]int, len(nums1))
    for i := 0; i < len(nums1); i++ {
        res[i] = greaterMap[nums1[i]]
    }
    return res
}

func calculateGreaterElement(nums []int) []int{
    // See above
}

var nextGreaterElement = function(nums1, nums2) {
    // Record the next greater element for each element in nums2
    let greater = calculateGreaterElement(nums2);
    // Convert to a mapping: element x -> x's next greater element
    let greaterMap = {};
    for (let i = 0; i < nums2.length; i++) {
        greaterMap[nums2[i]] = greater[i];
    }
    // nums1 is a subset of nums2, so we can get the result based on greaterMap
    let res = new Array(nums1.length);
    for (let i = 0; i < nums1.length; i++) {
        res[i] = greaterMap[nums1[i]];
    }
    return res;
};

var calculateGreaterElement = function(nums) {
    // See above
};

739. Daily Temperatures

Let's look at LeetCode problem #739, "Daily Temperatures":

You are given an array temperatures that contains the daily temperatures for the past few days. You need to return an array of the same length where each element represents the number of days you have to wait until a warmer temperature; if there's no warmer day ahead, fill it with 0. The function signature is as follows:

int[] dailyTemperatures(int[] temperatures);

vector<int> dailyTemperatures(vector<int>& temperatures);

def dailyTemperatures(temperatures: List[int]) -> List[int]:

func dailyTemperatures(temperatures []int) []int

var dailyTemperatures = function(temperatures) {}

For example, if you are given the input temperatures = [73,74,75,71,69,76], you should return [1,1,3,2,1,0]. This is because on the first day, the temperature is 73°F, and on the second day, it is 74°F, which is higher than 73°F. So, for the first day, you only need to wait one day to get a warmer temperature. The same logic applies to the subsequent days.

Essentially, this problem is about finding the next greater element. However, instead of asking for the value of the next greater element, it asks for the index distance from the current element to the next greater element.

Using the same approach, you can directly apply the monotonic stack algorithm template with slight modifications. Here is the code:

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] res = new int[n];
        // Store element indices here, not the elements themselves
        Stack<Integer> s = new Stack<>(); 
        // Monotonic stack template
        for (int i = n - 1; i >= 0; i--) {
            while (!s.isEmpty() && temperatures[s.peek()] <= temperatures[i]) {
                s.pop();
            }
            // Get the distance between indices
            res[i] = s.isEmpty() ? 0 : (s.peek() - i); 
            // Push the index onto the stack, not the element
            s.push(i); 
        }
        return res;
    }
}

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> res(n, 0);
        // Store element indices here, not elements
        stack<int> s;
        // Monotonic stack template
        for (int i = n - 1; i >= 0; i--) {
            while (!s.empty() && temperatures[s.top()] <= temperatures[i]) {
                s.pop();
            }
            // Get the distance between indices
            res[i] = s.empty() ? 0 : (s.top() - i);
            // Push the index onto the stack, not the element
            s.push(i); 
        }
        return res;
    }
};

class Solution:
    def dailyTemperatures(self, temperatures):
        n = len(temperatures)
        res = [0]*n
        # Store element indices here, not elements
        s = []
        # Monotonic stack template
        for i in range(n-1, -1, -1):
            while s and temperatures[s[-1]] <= temperatures[i]:
                s.pop()
            # Get the index difference
            res[i] = 0 if not s else s[-1] - i
            # Push the index onto the stack, not the element
            s.append(i)
        return res

func dailyTemperatures(temperatures []int) []int {
    n := len(temperatures)
    res := make([]int, n)
    s := make([]int, 0)
    
    // monotonic stack template
    for i := n - 1; i >= 0; i-- {
        for len(s) > 0 && temperatures[s[len(s)-1]] <= temperatures[i] {
            s = s[:len(s)-1]
        }
        
        // get the index distance
        if len(s) == 0 {
            res[i] = 0
        } else {
            res[i] = s[len(s)-1] - i 
        }
        
        // push the index onto the stack, not the element
        s = append(s, i) 
    }
    return res
}

var dailyTemperatures = function(temperatures) {
    let n = temperatures.length;
    let res = new Array(n).fill(0);
    // Store element indices here, not the elements themselves
    let s = [];
    // Monotonic stack template
    for (let i = n - 1; i >= 0; i--) {
        while (s.length > 0 && temperatures[s[s.length - 1]] <= temperatures[i]) {
            s.pop();
        }
        // Get the distance between indices
        res[i] = s.length === 0 ? 0 : (s[s.length - 1] - i); 
        // Push the index onto the stack, not the element
        s.push(i); 
    }
    return res;
};

The explanation of the monotonic stack is complete. Now, let's move on to another key topic: how to handle "circular arrays."

How to Handle Circular Arrays

The task is still to find the next greater element, but now assume the array is circular. How do you handle it? LeetCode problem #503 "Next Greater Element II" addresses this issue: given a "circular array," you need to find the next greater element for each element in the array.

For example, if the input is [2,1,2,4,3], you should return [4,2,4,-1,4]. Due to the circular nature, the last element 3 finds a greater element 4 after looping around.

If you have read the basic knowledge section on Circular Array Techniques, you should be familiar with this. We typically use the % operator (modulus) to simulate the circular effect:

int[] arr = {1,2,3,4,5};
int n = arr.length, index = 0;
while (true) {
    // Rotate in a circular array
    print(arr[index % n]);
    index++;
}

int main(){
    int arr[5] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]), index = 0;
    while (true) {
        // loop around in the circular array
        cout << arr[index % n] << endl;
        index++;
    }
    return 0;
}

arr = [1,2,3,4,5]
n = len(arr)
index = 0
while True:
    # Circulate in a circular array
    print(arr[index % n])
    index += 1

arr := []int{1, 2, 3, 4, 5}
n := len(arr)
index := 0
for {
    // Rotate in a circular array
    fmt.Println(arr[index % n])
    index++
}

var arr = [1,2,3,4,5];
var n = arr.length, index = 0;
while (true) {
    // Rotate in a circular array
    console.log(arr[index % n]);
    index++;
}

This problem should definitely be approached using the monotonic stack template, but the challenge lies in finding the next greater element for the last element, like how to find element 4 as the next greater element for 3 when the input is [2,1,2,4,3].

The common technique for this requirement is to effectively double the length of the array:

In doing so, element 3 can find element 4 as the next greater element, and all other elements can be correctly computed as well.

With this concept in mind, the simplest way to implement it is to construct this doubled-length array and apply the algorithm template. However, we can avoid creating a new array by using the technique of circular arrays to simulate the effect of doubling the array length. Let's take a look at the code directly:

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Stack<Integer> s = new Stack<>();
        // Double the array length to simulate a circular array
        for (int i = 2 * n - 1; i >= 0; i--) {
            // Index i needs to be modulo, the rest is the same as the template
            while (!s.isEmpty() && s.peek() <= nums[i % n]) {
                s.pop();
            }
            res[i % n] = s.isEmpty() ? -1 : s.peek();
            s.push(nums[i % n]);
        }
        return res;
    }
}

class Solution {
public:
   vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        stack<int> s;
        // Double the array length to simulate a circular array
        for (int i = 2 * n - 1; i >= 0; i--) {
            // Index i needs to be modulated, the rest is the same as the template
            while (!s.empty() && s.top() <= nums[i % n]) {
                s.pop();
            }
            res[i % n] = s.empty() ? -1 : s.top();
            s.push(nums[i % n]);
        }
        return res;
    }
};

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = [0] * n
        # Use an array to simulate a stack
        s = []
        # Double the array length to simulate a circular array
        for i in range(2 * n - 1, -1, -1):
            # Index i needs to be modulo, the rest is the same as the template
            while s and s[-1] <= nums[i % n]:
                s.pop()
            res[i % n] = -1 if not s else s[-1]
            s.append(nums[i % n])
        return res

func nextGreaterElements(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    // use an array to simulate a stack
    s := make([]int, 0)

    // double the array length to simulate a circular array
    for i := 2 * n - 1; i >= 0; i-- {
        // index i needs to be modulo, the rest is the same as the template
        for len(s) > 0 && s[len(s)-1] <= nums[i % n] {
            s = s[:len(s)-1] // pop element from stack
        }
        
        if len(s) == 0 {
            res[i % n] = -1
        } else {
            res[i % n] = s[len(s) - 1]
        }
        
        s = append(s, nums[i % n]) // push element to stack
    }
    
    return res
}

var nextGreaterElements = function(nums) {
    let n = nums.length;
    let res = new Array(n);
    // use array to simulate a stack
    let s = [];
    // double the array length to simulate a circular array
    for (let i = 2 * n - 1; i >= 0; i--) {
        // index i needs modulo, the rest is the same as the template
        while (s.length !== 0 && s[s.length - 1] <= nums[i % n]) {
            s.pop();
        }
        res[i % n] = s.length === 0 ? -1 : s[s.length - 1];
        s.push(nums[i % n]);
    }
    return res;
};

This approach allows us to cleverly solve the problem of circular arrays with a time complexity of $O(N)$.

Let's raise some questions. The monotonic stack template provided in this article is the nextGreaterElement function, which can calculate the next greater element for each item. But what if you need to calculate the previous greater element, or the previous greater or equal element? How should you modify the template accordingly? Moreover, in practical applications, problems won't directly ask you to calculate the next (or previous) greater (or smaller) element. How can you transform the problem into one related to monotonic stacks?

I will compare different forms of monotonic stacks and provide classic examples in Variants and Exercises of Monotonic Stacks. For more design-related data structure problems, refer to Classic Exercises in Data Structure Design.