单调栈算法模板解决三道例题

labuladong原创数据结构单调栈约 3615 字

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	Difficulty
496. Next Greater Element I	🟢
503. Next Greater Element II	🟠
739. Daily Temperatures	🟠

Prerequisites

Before reading this article, you should learn:

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:

java 🟢

int[] calculateGreaterElement(int[] nums);

cpp 🤖

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

python 🤖

def calculateGreaterElement(nums: List[int])

go 🤖

func calculateGreaterElement(nums []int) []int

javascript 🤖

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 a larger number 4; 1 is followed by a larger number 2; the second 2 is followed by a larger number 4; there is no number larger than 4 after it, so we fill -1; similarly, there is no number larger than 3 after it, so we fill -1.

The brute-force solution for this problem is straightforward: scan each element to find the first larger element that follows it. However, the time complexity of the brute-force approach is O(n^2).

We can think of this problem abstractly: imagine the elements of the array as people standing in a line, with their values representing their heights. These people are facing you. How do you find the next greater element for the value '2'? It's simple: if you can see the element '2', then the first person visible behind '2' is the next greater element. This is because any shorter person (smaller value) is obscured by '2', and the first one that appears is the answer.

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

java 🟢

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;
}

cpp 🤖

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;
}

python 🤖

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

go 🤖

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
}

javascript 🤖

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 should scan elements from back to front because we utilize the stack structure. Pushing elements in reverse is equivalent to popping them in the correct order. The while loop removes elements between two "taller" elements, as their presence is meaningless. With a "taller" element blocking them, they cannot be the next greater element for subsequent incoming elements.

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

To analyze its time complexity, consider the overall process: There are n elements in total, each of which is pushed onto the stack once and popped at most once, with no redundant operations. Therefore, the total computational scale is directly proportional to the number of elements n, resulting in an O(n) complexity.

Problem Variations

The implementation of a monotonic stack is relatively simple. Let's look at some specific problems.

496. Next Greater Element I

First, a simple variation, LeetCode problem 496 "Next Greater Element I":

496. Next Greater Element I | 力扣 | LeetCode |

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Example 1:

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.

Example 2:

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.

Constraints:

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 10⁴
All integers in nums1 and nums2 are unique.
All the integers of nums1 also appear in nums2.

Follow up: Could you find an O(nums1.length + nums2.length) solution?

This problem gives you two input arrays, nums1 and nums2, and asks you to find the next greater element for each element in nums1 within nums2. The function signature is as follows:

java 🟢

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

cpp 🤖

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

python 🤖

from typing import List

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

go 🤖

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

javascript 🤖

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:

java 🟢

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
    }
}

cpp 🤖

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
    }
};

python 🤖

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

go 🤖

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
}

javascript 🤖

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:

java 🟢

int[] dailyTemperatures(int[] temperatures);

cpp 🤖

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

python 🤖

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

go 🤖

func dailyTemperatures(temperatures []int) []int

javascript 🤖

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:

java 🟢

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;
    }
}

cpp 🤖

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;
    }
};

python 🤖

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

go 🤖

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
}

javascript 🤖

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:

java 🟢

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++;
}

cpp 🤖

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;
}

python 🤖

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

go 🤖

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

javascript 🤖

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 definitely requires using the monotonic stack solution template. However, the challenge lies in cases like the input [2,1,2,4,3]. For the last element 3, how do you find the element 4 as the next greater element?

A common approach for such requirements is to double the length of the array:

This way, element 3 can find element 4 as the next greater element, and all other elements can be correctly calculated.

With this idea, the simplest implementation would be to construct this doubled-length array and then apply the algorithm template. However, we can avoid constructing a new array and instead use a circular array technique to simulate the effect of doubling the array length. Let's see the code:

java 🟢

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;
    }
}

cpp 🤖

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;
    }
};

python 🤖

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

go 🤖

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
}

javascript 🤖

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 way, you can cleverly solve the problem of circular arrays with a time complexity of O(N).

Finally, let's pose some questions. The monotonic stack template provided in this article is the nextGreaterElement function, which calculates the next greater element for each element. But what if the problem asks you to find the previous greater element, or the previous greater or equal element? How would 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 do you transform the problem into one related to monotonic stacks?

I will discuss several variants of the monotonic stack and provide exercises in Variants and Exercises of Monotonic Stack, and present classic examples of monotonic stack problems. For more data structure design problems, refer to Classic Data Structure Design Exercises.

引用本文的题目

安装我的 Chrome 刷题插件点开下列题目可直接查看解题思路：

LeetCode	力扣
1019. Next Greater Node In Linked List	1019. 链表中的下一个更大节点
1944. Number of Visible People in a Queue	1944. 队列中可以看到的人数
402. Remove K Digits	402. 移掉 K 位数字
42. Trapping Rain Water	42. 接雨水
901. Online Stock Span	901. 股票价格跨度
918. Maximum Sum Circular Subarray	918. 环形子数组的最大和

单调栈算法模板解决三道例题

496. 下一个更大元素 I https://leetcode.cn/problems/next-greater-element-i

496. Next Greater Element I https://leetcode.com/problems/next-greater-element-i

503. 下一个更大元素 II https://leetcode.cn/problems/next-greater-element-ii

503. Next Greater Element II https://leetcode.com/problems/next-greater-element-ii

739. 每日温度 https://leetcode.cn/problems/daily-temperatures

739. Daily Temperatures https://leetcode.com/problems/daily-temperatures

剑指 Offer II 038. 每日温度 https://leetcode.cn/problems/iIQa4I

剑指 Offer II 038. 每日温度 https://leetcode.com/problems/iIQa4I

Monotonic Stack Template

Problem Variations

496. Next Greater Element I

739. Daily Temperatures

How to Handle Circular Arrays