目录

题目要求解题思路labuladong的模板单调栈循环数组 java代码（HashMap + 单调栈模板）

参考：单调栈解决 Next Greater Number 一类问题

题目要求

给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

输入: nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出: [-1,3,-1] 解释: 对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。 对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。 对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。

原题链接：496. 下一个更大元素 I

类似的题目：503. 下一个更大元素 II 1118.一月有多少天

解题思路

对于一个数组：

[1,3,4,2]

1的右边第一个最大数为3，3的右边第一个最大数为4，4无，2无；这可以看成一个比身高的问题：将数组元素看成并排站的四个人，元素大小看成其身高，对于1而言，其最后回头可见的第一个人就是3，但是对于4来说，回头并无法见到比他更高的人。

labuladong的模板

单调栈

vector<int> nextGreaterElement(vector<int>& nums) { vector<int> ans(nums.size()); // 存放答案的数组 stack<int> s; for (int i = nums.size() - 1; i >= 0; i--) { // 倒着往栈里放 while (!s.empty() && s.top() <= nums[i]) { // 判定个子高矮 s.pop(); // 矮个起开，反正也被挡着了。。。 } ans[i] = s.empty() ? -1 : s.top(); // 这个元素身后的第一个高个 s.push(nums[i]); // 进队，接受之后的身高判定吧！ } return ans; }

如果用暴力解，则需要两次for循环，时间复杂度高达$O(n^2)$。以上代码虽然是for+while，但是对于n个元素，每个元素只入栈一次，且最多被pop一次，计算量和元素量是成正比的，所以以上的模板时间复杂度为$O(n)$。

循环数组

思路其实和单调栈思路相同，只是在循环数组中，该元素不仅要和其右边的元素进行比较，同时也要和左边元素比较。原有的[1,3,4,2]数组可以看成[1,3,4,2,1,3,4,2]。一般是通过取模操作解决环形队列问题。

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

详见题解：参考：单调栈解决 Next Greater Number 一类问题

java代码（HashMap + 单调栈模板）

class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { int[] result = new int[nums1.length]; Map<Integer, Integer> map = nextGreaterHelper(nums2); for (int i = 0; i < nums1.length; i++) { result[i] = map.get(nums1[i]); // 由于第一个数组是第二个数组的子集，因此直接通过map直接匹配结果 } return result; } private Map<Integer, Integer> nextGreaterHelper(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); Stack<Integer> stack = new Stack<>(); // 存放较大的数 for (int i = nums.length - 1; i >= 0; i--) { // 倒序遍历 while (!stack.isEmpty() && stack.peek() <= nums[i]) { // 将比nums[i]小或者相等的数字pop出，出现大数，则该栈顶则为当前元素的右端第一个最大值 stack.pop(); } // 栈为空则说明没有该元素右边没有比它更大的数字，不为空则栈顶即为结果 map.put(nums[i], stack.isEmpty() ? -1 : stack.peek()); // 将结果放入map中，方便索引 stack.push(nums[i]); // 进栈 } return map; } }