LeetCode | 力扣 | 难度 |
🟢 | ||
🟠 | ||
🟠 | ||
- | 🟠 |
一 单调栈模板
问题：输入一个数组
nums，请你返回一个等长的结果数组，结果数组中对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。比如说，输入一个数组
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。
建立单调栈
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; }
for 循环要从后往前扫描元素，因为我们借助的是栈的结构，倒着入栈，其实是正着出栈。while 循环是把两个「个子高」元素之间的元素排除，因为他们的存在没有意义，前面挡着个「更高」的元素，所以他们不可能被作为后续进来的元素的下一个更大元素了。
输入为 1，3，4，2
求出的单调栈为 3，4，-1，-1
二 扩展变形
1. 环形队列
针对环形数组求下一个最大值，可以看作是普通数组遍历两次，即可将最后的节点找到对应的下一个最大值。
通过 % 运算符求模（余数），来模拟环形特效
public 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--) { 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; }