题目描述
这是 LeetCode 上的 503. 下一个更大元素 II ，难度为 中等。
Tag : 「单调栈」
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:
输入: [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2； 数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。 复制代码
单调栈解法
对于「找最近一个比当前值大/小」的问题，都可以使用单调栈来解决。
单调栈就是在栈的基础上维护一个栈内元素单调。
在理解单调栈之前，我们先回想一下「朴素解法」是如何解决这个问题的。
对于每个数而言，我们需要遍历其右边的数，直到找到比自身大的数，这是一个 O(n^2)O(n2) 的做法。
之所以是 O(n^2)O(n2)，是因为每次找下一个最大值，我们是通过「主动」遍历来实现的。
而如果使用的是单调栈的话，可以做到 O(n)O(n) 的复杂度，我们将当前还没得到答案的下标暂存于栈内，从而实现「被动」更新答案。
也就是说，栈内存放的永远是还没更新答案的下标。
具体的做法是：
每次将当前遍历到的下标存入栈内，将当前下标存入栈内前，检查一下当前值是否能够作为栈内位置的答案（即成为栈内位置的「下一个更大的元素」），如果可以，则将栈内下标弹出。
如此一来，我们便实现了「被动」更新答案，同时由于我们的弹栈和出栈逻辑，决定了我们整个过程中栈内元素单调。
还有一些编码细节，由于我们要找每一个元素的下一个更大的值，因此我们需要对原数组遍历两次，对遍历下标进行取余转换。
以及因为栈内存放的是还没更新答案的下标，可能会有位置会一直留在栈内（最大值的位置），因此我们要在处理前预设答案为 -1。而从实现那些没有下一个更大元素（不出栈）的位置的答案是 -1。
代码：
class Solution { public int[] nextGreaterElements(int[] nums) { int n = nums.length; int[] ans = new int[n]; Arrays.fill(ans, -1); Deque<Integer> d = new ArrayDeque<>(); for (int i = 0; i < n * 2; i++) { while (!d.isEmpty() && nums[i % n] > nums[d.peekLast()]) { int u = d.pollLast(); ans[u] = nums[i % n]; } d.addLast(i % n); } return ans; } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(n)O(n)
卡常小技巧
本题不需要用到这个技巧，但是还是介绍一下，可作为拓展。
我们可以使用静态数组来模拟栈，这样我们的代码将会更快一点：
class Solution { public int[] nextGreaterElements(int[] nums) { int n = nums.length; int[] ans = new int[n]; Arrays.fill(ans, -1); // 使用数组模拟栈，hh 代表栈底，tt 代表栈顶 int[] d = new int[n * 2]; int hh = 0, tt = -1; for (int i = 0; i < n * 2; i++) { while (hh <= tt && nums[i % n] > nums[d[tt]]) { int u = d[tt--]; ans[u] = nums[i % n]; } d[++tt] = i % n; } return ans; } } 复制代码
总结
要从逻辑上去理解为什么能用「单调栈」解决问题：
- 我们希望将 O(n^2)O(n2) 算法优化为 O(n)O(n) 算法，因此需要将「主动」获取答案转换为「被动」更新
- 我们需要使用数据结构保持那些「尚未更新」的位置下标，由于题目要求的是找「下一个更大的元素」，因此使用栈来保存
- 「被动」更新答案的逻辑导致了我们栈内元素单调
最后
这是我们「刷穿 LeetCode」系列文章的第 No.501 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
