单调栈结构解决三道算法题
数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 496. Next Greater Element I | 496. 下一个更大元素 I | 🟢 |
| 503. Next Greater Element II | 503. 下一个更大元素 II | 🟠 |
| 739. Daily Temperatures | 739. 每日温度 | 🟠 |
| - | 剑指 Offer II 038. 每日温度 | 🟠 |
———–
栈（stack）是很简单的一种数据结构，先进后出的逻辑顺序，符合某些问题的特点，比如说函数调用栈。单调栈实际上就是栈，只是利用了一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。
听起来有点像堆（heap）？不是的，单调栈用途不太广泛，只处理一类典型的问题，比如「下一个更大元素」，「上一个更小元素」等。本文用讲解单调队列的算法模版解决「下一个更大元素」相关问题，并且探讨处理「循环数组」的策略。至于其他的变体和经典例题，我会在 数据结构精品课 中讲解。
单调栈模板
现在给你出这么一道题：输入一个数组 nums，请你返回一个等长的结果数组，结果数组中对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。函数签名如下：
int[] nextGreaterElement(int[] nums);
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
vector<int> nextGreaterElement(vector<int>& nums);
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def nextGreaterElement(nums: List[int]) -> List[int]:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func nextGreaterElement(nums []int) []int {
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var nextGreaterElement = function(nums) {
// function body here
};
比如说，输入一个数组 nums = [2,1,2,4,3]，你返回数组 [4,2,4,-1,-1]。因为第一个 2 后面比 2 大的数是 4; 1 后面比 1 大的数是 2；第二个 2 后面比 2 大的数是 4; 4 后面没有比 4 大的数，填 -1；3 后面没有比 3 大的数，填 -1。
这道题的暴力解法很好想到，就是对每个元素后面都进行扫描，找到第一个更大的元素就行了。但是暴力解法的时间复杂度是 O(n^2)。
这个问题可以这样抽象思考：把数组的元素想象成并列站立的人，元素大小想象成人的身高。这些人面对你站成一列，如何求元素「2」的下一个更大元素呢？很简单，如果能够看到元素「2」，那么他后面可见的第一个人就是「2」的下一个更大元素，因为比「2」小的元素身高不够，都被「2」挡住了，第一个露出来的就是答案。
这个情景很好理解吧？带着这个抽象的情景，先来看下代码。
int[] nextGreaterElement(int[] nums) {
int n = nums.length;
// 存放答案的数组
int[] res = new int[n];
Stack<Integer> s = new Stack<>();
// 倒着往栈里放
for (int i = n - 1; i >= 0; i--) {
// 判定个子高矮
while (!s.isEmpty() && s.peek() <= nums[i]) {
// 矮个起开，反正也被挡着了。。。
s.pop();
}
// nums[i] 身后的更大元素
res[i] = s.isEmpty() ? -1 : s.peek();
s.push(nums[i]);
}
return res;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
#include <stack>
#include <vector>
std::vector<int> nextGreaterElement(std::vector<int>& nums) {
int n = nums.size();
// 存放答案的数组
std::vector<int> res(n);
std::stack<int> s;
// 倒着往栈里放
for (int i = n - 1; i >= 0; i--) {
// 判定个子高矮
while (!s.empty() && s.top() <= nums[i]) {
// 矮个起开，反正也被挡着了。。。
s.pop();
}
// nums[i] 身后的更大元素
res[i] = s.empty() ? -1 : s.top();
s.push(nums[i]);
}
return res;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def nextGreaterElement(nums: List[int]) -> List[int]:
n = len(nums)
# 存放答案的数组
res = [0 for _ in range(n)]
s = []
# 倒着往栈里放
for i in range(n - 1, -1, -1):
# 判定个子高矮
while s and s[-1] <= nums[i]:
# 矮个起开，反正也被挡着了。。。
s.pop()
# nums[i] 身后的更大元素
res[i] = s[-1] if s else -1
s.append(nums[i])
return res
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func nextGreaterElement(nums []int) []int {
n := len(nums)
// 存放答案的数组
res := make([]int, n)
// 倒着往栈里放
s := make([]int, 0)
for i := n - 1; i >= 0; i-- {
// 判定个子高矮
for len(s) > 0 && s[len(s)-1] <= nums[i] {
// 矮个起开，反正也被挡着了。。。
s = s[:len(s)-1]
}
// nums[i] 身后的更大元素
if len(s) == 0 {
res[i] = -1
} else {
res[i] = s[len(s)-1]
}
s = append(s, nums[i])
}
return res
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var nextGreaterElement = function(nums) {
var n = nums.length;
// 存放答案的数组
var res = new Array(n).fill(0);
var s = [];
// 倒着往栈里放
for (var i = n - 1; i >= 0; i--) {
// 判定个子高矮
while (s.length && s[s.length - 1] <= nums[i]) {
// 矮个起开，反正也被挡着了。。。
s.pop();
}
// nums[i] 身后的更大元素
res[i] = s.length ? s[s.length - 1] : -1;
s.push(nums[i]);
}
return res;
};
这就是单调队列解决问题的模板。for 循环要从后往前扫描元素，因为我们借助的是栈的结构，倒着入栈，其实是正着出栈。while 循环是把两个「个子高」元素之间的元素排除，因为他们的存在没有意义，前面挡着个「更高」的元素，所以他们不可能被作为后续进来的元素的下一个更大元素了。
这个算法的时间复杂度不是那么直观，如果你看到 for 循环嵌套 while 循环，可能认为这个算法的复杂度也是 O(n^2)，但是实际上这个算法的复杂度只有 O(n)。
分析它的时间复杂度，要从整体来看：总共有 n 个元素，每个元素都被 push 入栈了一次，而最多会被 pop 一次，没有任何冗余操作。所以总的计算规模是和元素规模 n 成正比的，也就是 O(n) 的复杂度。
问题变形
单调栈的使用技巧差不多了，首先来一个简单的变形，力扣第 496 题「 下一个更大元素 I」：
这道题给你输入两个数组 nums1 和 nums2，让你求 nums1 中的元素在 nums2 中的下一个更大元素，函数签名如下：
int[] nextGreaterElement(int[] nums1, int[] nums2)
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
int* nextGreaterElement(int* nums1, int* nums2, int nums1Size, int nums2Size)
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def nextGreaterElement(nums1: List[int], nums2: List[int]) -> List[int]:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func nextGreaterElement(nums1 []int, nums2 []int) []int {
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var nextGreaterElement = function(nums1, nums2) {
// function body here
};
其实和把我们刚才的代码改一改就可以解决这道题了，因为题目说 nums1 是 nums2 的子集，那么我们先把 nums2 中每个元素的下一个更大元素算出来存到一个映射里，然后再让 nums1 中的元素去查表即可：
int[] nextGreaterElement(int[] nums1, int[] nums2) {
// 记录 nums2 中每个元素的下一个更大元素
int[] greater = nextGreaterElement(nums2);
// 转化成映射：元素 x -> x 的下一个最大元素
HashMap<Integer, Integer> greaterMap = new HashMap<>();
for (int i = 0; i < nums2.length; i++) {
greaterMap.put(nums2[i], greater[i]);
}
// nums1 是 nums2 的子集，所以根据 greaterMap 可以得到结果
int[] res = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
res[i] = greaterMap.get(nums1[i]);
}
return res;
}
int[] nextGreaterElement(int[] nums) {
// 见上文
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
// 记录 nums2 中每个元素的下一个更大元素
vector<int> greater = nextGreaterElement(nums2);
// 转化成映射：元素 x -> x 的下一个最大元素
unordered_map<int, int> greaterMap;
for (int i = 0; i < nums2.size(); i++) {
greaterMap[nums2[i]] = greater[i];
}
// nums1 是 nums2 的子集，所以根据 greaterMap 可以得到结果
vector<int> res(nums1.size());
for (int i = 0; i < nums1.size(); i++) {
res[i] = greaterMap[nums1[i]];
}
return res;
}
vector<int> nextGreaterElement(vector<int>& nums) {
// 见上文
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def nextGreaterElement(nums1: List[int], nums2: List[int]) -> List[int]:
def nextGreater(nums: List[int]) -> List[int]:
# 实现代码
greater = nextGreater(nums2)
greaterMap = {}
for i in range(len(nums2)):
greaterMap[nums2[i]] = greater[i]
res = [0] * len(nums1)
for i in range(len(nums1)):
res[i] = greaterMap[nums1[i]]
return res
def nextGreater(nums: List[int]) -> List[int]:
# 实现代码
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func nextGreaterElement(nums1 []int, nums2 []int) []int {
greater := nextGreaterElement(nums2)
greaterMap := make(map[int]int, len(nums2))
for i := 0; i < len(nums2); i++ {
greaterMap[nums2[i]] = greater[i]
}
res := make([]int, len(nums1))
for i := 0; i < len(nums1); i++ {
res[i] = greaterMap[nums1[i]]
}
return res
}
func nextGreaterElement(nums []int) []int {
// 见上文
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var nextGreaterElement = function(nums1, nums2) {
function nextGreaterElementHelper(nums) {
// 见上文
}
// 记录 nums2 中每个元素的下一个更大元素
var greater = nextGreaterElementHelper(nums2);
// 转化成映射：元素 x -> x 的下一个最大元素
var greaterMap = new Map();
for (var i = 0; i < nums2.length; i++) {
greaterMap.set(nums2[i], greater[i]);
}
// nums1 是 nums2 的子集，所以根据 greaterMap 可以得到结果
var res = new Array(nums1.length);
for (var i = 0; i < nums1.length; i++) {
res[i] = greaterMap.get(nums1[i]);
}
return res;
};
🎃 代码可视化动画 🎃
再看看力扣第 739 题「 每日温度」：
给你一个数组 temperatures，这个数组存放的是近几天的天气气温，你返回一个等长的数组，计算：对于每一天，你还要至少等多少天才能等到一个更暖和的气温；如果等不到那一天，填 0。函数签名如下：
int[] dailyTemperatures(int[] temperatures);
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
vector<int> dailyTemperatures(vector<int>& temperatures);
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def dailyTemperatures(temperatures: List[int]) -> List[int]:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func dailyTemperatures(temperatures []int) []int {
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var dailyTemperatures = function(temperatures) {
// function body here
}
比如说给你输入 temperatures = [73,74,75,71,69,76]，你返回 [1,1,3,2,1,0]。因为第一天 73 华氏度，第二天 74 华氏度，比 73 大，所以对于第一天，只要等一天就能等到一个更暖和的气温，后面的同理。
这个问题本质上也是找下一个更大元素，只不过现在不是问你下一个更大元素的值是多少，而是问你当前元素距离下一个更大元素的索引距离而已。
相同的思路，直接调用单调栈的算法模板，稍作改动就可以，直接上代码吧：
int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
// 这里放元素索引，而不是元素
Stack<Integer> s = new Stack<>();
/* 单调栈模板 */
for (int i = n - 1; i >= 0; i--) {
while (!s.isEmpty() && temperatures[s.peek()] <= temperatures[i]) {
s.pop();
}
// 得到索引间距
res[i] = s.isEmpty() ? 0 : (s.peek() - i);
// 将索引入栈，而不是元素
s.push(i);
}
return res;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
vector<int> res(n);
// 这里放元素索引，而不是元素
stack<int> s;
/* 单调栈模板 */
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && temperatures[s.top()] <= temperatures[i]) {
s.pop();
}
// 得到索引间距
res[i] = s.empty() ? 0 : (s.top() - i);
// 将索引入栈，而不是元素
s.push(i);
}
return res;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
from typing import List
def dailyTemperatures(temperatures: List[int]) -> List[int]:
n = len(temperatures)
res = [0] * n
# 这里放元素索引，而不是元素
s = []
# 单调栈模板
for i in range(n-1, -1, -1):
while s and temperatures[s[-1]] <= temperatures[i]:
s.pop()
# 得到索引间距
res[i] = s[-1] - i if s else 0
# 将索引入栈，而不是元素
s.append(i)
return res
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func dailyTemperatures(temperatures []int) []int {
n := len(temperatures)
res := make([]int, n)
// 这里放元素索引，而不是元素
s := make([]int, 0)
/* 单调栈模板 */
for i := n - 1; i >= 0; i-- {
for len(s) > 0 && temperatures[s[len(s)-1]] <= temperatures[i] {
s = s[:len(s)-1]
}
// 得到索引间距
if len(s) == 0 {
res[i] = 0
} else {
res[i] = s[len(s)-1] - i
}
// 将索引入栈，而不是元素
s = append(s, i)
}
return res
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var dailyTemperatures = function(temperatures) {
var n = temperatures.length;
var res = new Array(n).fill(0);
// 这里放元素索引，而不是元素
var s = [];
/* 单调栈模板 */
for (var i = n - 1; i >= 0; i--) {
while (s.length && temperatures[s[s.length-1]] <= temperatures[i]) {
s.pop();
}
// 得到索引间距
res[i] = !s.length ? 0 : (s[s.length-1] - i);
// 将索引入栈，而不是元素
s.push(i);
}
return res;
};
单调栈讲解完毕，下面开始另一个重点：如何处理「循环数组」。
如何处理环形数组
同样是求下一个更大元素，现在假设给你的数组是个环形的，如何处理？力扣第 503 题「 下一个更大元素 II」就是这个问题：输入一个「环形数组」，请你计算其中每个元素的下一个更大元素。
比如输入 [2,1,2,4,3]，你应该返回 [4,2,4,-1,4]，因为拥有了环形属性，最后一个元素 3 绕了一圈后找到了比自己大的元素 4。
我们一般是通过 % 运算符求模（余数），来模拟环形特效：
int[] arr = {1,2,3,4,5};
int n = arr.length, index = 0;
while (true) {
// 在环形数组中转圈
print(arr[index % n]);
index++;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
int arr[] = {1,2,3,4,5};
int n = sizeof(arr) / sizeof(arr[0]), index = 0;
while (true) {
// 在环形数组中转圈
cout << arr[index % n] << endl;
index++;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
arr = [1, 2, 3, 4, 5]
n, index = len(arr), 0
while True:
# 在环形数组中转圈
print(arr[index % n])
index += 1
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
arr := []int{1, 2, 3, 4, 5}
n, index := len(arr), 0
for {
// 在环形数组中转圈
fmt.Println(arr[index%n])
index++
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var arr = [1, 2, 3, 4, 5];
var n = arr.length,
index = 0;
while (true) {
// 在环形数组中转圈
console.log(arr[index % n]);
index++;
}
这个问题肯定还是要用单调栈的解题模板，但难点在于，比如输入是 [2,1,2,4,3]，对于最后一个元素 3，如何找到元素 4 作为下一个更大元素。
对于这种需求，常用套路就是将数组长度翻倍：
这样，元素 3 就可以找到元素 4 作为下一个更大元素了，而且其他的元素都可以被正确地计算。
有了思路，最简单的实现方式当然可以把这个双倍长度的数组构造出来，然后套用算法模板。但是，我们可以不用构造新数组，而是利用循环数组的技巧来模拟数组长度翻倍的效果。直接看代码吧：
int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Stack<Integer> s = new Stack<>();
// 数组长度加倍模拟环形数组
for (int i = 2 * n - 1; i >= 0; i--) {
// 索引 i 要求模，其他的和模板一样
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 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> res(n);
stack<int> s;
// 数组长度加倍模拟环形数组
for (int i = 2 * n - 1; i >= 0; i--) {
// 索引 i 要求模，其他的和模板一样
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 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
from typing import List
def nextGreaterElements(nums: List[int]) -> List[int]:
n = len(nums)
res = [-1]*n
s = []
# 数组长度加倍模拟环形数组
for i in range(2*n-1, -1, -1):
# 索引 i 要求模，其他的和模板一样
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 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func nextGreaterElements(nums []int) []int {
n := len(nums)
res := make([]int, n)
var stack []int
// 数组长度加倍模拟环形数组
for i := 2*n - 1; i >= 0; i-- {
// 索引 i 要求模，其他的和模板一样
for len(stack) > 0 && stack[len(stack)-1] <= nums[i%n] {
stack = stack[:len(stack)-1]
}
if len(stack) == 0 {
res[i%n] = -1
} else {
res[i%n] = stack[len(stack)-1]
}
stack = append(stack, nums[i%n])
}
return res
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var nextGreaterElements = function(nums) {
var n = nums.length;
var res = new Array(n).fill(0);
var s = [];
// 数组长度加倍模拟环形数组
for (var i = 2 * n - 1; i >= 0; i--) {
// 索引 i 要求模，其他的和模板一样
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;
};
🌟 代码可视化动画 🌟
这样，就可以巧妙解决环形数组的问题，时间复杂度 O(N)。
最后提出一些问题吧，本文提供的单调栈模板是 nextGreaterElement 函数，可以计算每个元素的下一个更大元素，但如果题目让你计算上一个更大元素，或者计算上一个更大或相等的元素，应该如何修改对应的模板呢？而且在实际应用中，题目不会直接让你计算下一个（上一个）更大（小）的元素，你如何把问题转化成单调栈相关的问题呢？
我会在 单调栈的几种变体 对比单调栈的几种其他形式，并在 单调栈的运用 中给出单调栈的经典例题。更多数据结构设计类题目参见 数据结构设计经典习题。
引用本文的题目
安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：
引用本文的文章
＿＿＿＿＿＿＿＿＿＿＿＿＿
《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：
共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释