496. 下一个更大元素 I
题目描述
输入两个数组 nums1 和 nums2，各自内部没有重复值，并且 nums1 的每个元素都在 nums2 中出现。
对 nums1 中的每个数 x，先找到它在 nums2 中的位置，然后从这个位置往右看，第一个大于 x 的数就是它的下一个更大元素；如果右边没有更大的数，则记为 -1。
返回与 nums1 等长的数组 ans，ans[i] 是 nums1[i] 的下一个更大元素。
示例 1
输入：nums1 = [4,1,2], nums2 = [1,3,4,2] 输出：[-1,3,-1]
解释：4 在 nums2 中右边只有 2，记 -1；1 右边第一个更大的是 3；2 在末尾，记 -1。
示例 2
输入：nums1 = [2,4], nums2 = [1,2,3,4] 输出：[3,-1]
解释：2 右边第一个更大的是 3；4 在末尾，记 -1。
数据范围
1 <= nums1.length <= nums2.length <= 10000 <= nums1[i], nums2[i] <= 10^4nums1与nums2中的所有数互不相同。nums1的每个数都出现在nums2中。
进阶：能否设计出 O(nums1.length + nums2.length) 的解法？
解题思路：单调栈 + 哈希表
对 nums2 用单调栈一遍算出每个数的“下一个更大元素”。栈里存还没找到答案的数，从底到顶递减。新数 x 到来时，栈顶若比 x 小，x 就是它右边第一个更大的数，弹出并记入哈希表；一直弹到栈顶不小于 x，再把 x 压入。最后 nums1 的每个数查表即可，查不到就是 -1。
为什么正确
栈中元素从底到顶严格递减，它们都是“右边暂时还没出现更大数”的元素。
复杂度分析
时间 O(m + n)（每个数入栈出栈各一次），空间 O(n)。
易错点
比较是严格大于。另外不要对 nums1 的每个数都在 nums2 里向右暴力找，那是 O(mn)；单调栈一次性算好所有答案。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
nxt = {}
stack = []
for x in nums2:
while stack and stack[-1] < x:
nxt[stack.pop()] = x
stack.append(x)
return [nxt.get(x, -1) for x in nums1]class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> nxt = new HashMap<>();
Deque<Integer> stack = new ArrayDeque<>();
for (int x : nums2) {
while (!stack.isEmpty() && stack.peek() < x) {
nxt.put(stack.pop(), x);
}
stack.push(x);
}
int[] res = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) res[i] = nxt.getOrDefault(nums1[i], -1);
return res;
}
}class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> nxt;
vector<int> stack;
for (int x : nums2) {
while (!stack.empty() && stack.back() < x) {
nxt[stack.back()] = x;
stack.pop_back();
}
stack.push_back(x);
}
vector<int> res;
for (int x : nums1) res.push_back(nxt.count(x) ? nxt[x] : -1);
return res;
}
};func nextGreaterElement(nums1 []int, nums2 []int) []int {
nxt := map[int]int{}
stack := []int{}
for _, x := range nums2 {
for len(stack) > 0 && stack[len(stack)-1] < x {
nxt[stack[len(stack)-1]] = x
stack = stack[:len(stack)-1]
}
stack = append(stack, x)
}
res := make([]int, len(nums1))
for i, x := range nums1 {
if v, ok := nxt[x]; ok {
res[i] = v
} else {
res[i] = -1
}
}
return res
}var nextGreaterElement = function(nums1, nums2) {
const nxt = new Map();
const stack = [];
for (const x of nums2) {
while (stack.length && stack[stack.length - 1] < x) {
nxt.set(stack.pop(), x);
}
stack.push(x);
}
return nums1.map(x => nxt.has(x) ? nxt.get(x) : -1);
};function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
const nxt = new Map<number, number>();
const stack: number[] = [];
for (const x of nums2) {
while (stack.length && stack[stack.length - 1] < x) {
nxt.set(stack.pop()!, x);
}
stack.push(x);
}
return nums1.map(x => nxt.has(x) ? nxt.get(x)! : -1);
}其他解法
暴力法对每个查询独立向右扫描；单调栈一次遍历 nums2 就求出所有数的下一个更大元素，再用哈希表 O(1) 回答查询，是“下一个更大元素”问题的标准模板。
解法 2：暴力查找 时间 O(mn)，空间 O(1)
对 nums1 中的每个数 x，先在 nums2 中找到它的位置，再从下一个位置开始向右扫描，遇到第一个比 x 大的数就是答案，扫到末尾都没有则为 −1。
完全按题意模拟，不需要额外空间，也不需要理解单调栈。每次查询都可能扫描整个 nums2，总复杂度是平方级。
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
ans = []
for x in nums1:
# 先找到 x 在 nums2 中的位置，再向右找第一个更大的数
j = nums2.index(x) + 1
while j < len(nums2) and nums2[j] <= x:
j += 1
ans.append(nums2[j] if j < len(nums2) else -1)
return ansclass Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int n = nums2.length;
int[] ans = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
int x = nums1[i], j = 0;
while (nums2[j] != x) j++;
j++;
while (j < n && nums2[j] <= x) j++;
ans[i] = j < n ? nums2[j] : -1;
}
return ans;
}
}class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
int n = nums2.size();
vector<int> ans;
for (int x : nums1) {
int j = find(nums2.begin(), nums2.end(), x) - nums2.begin() + 1;
while (j < n && nums2[j] <= x) j++;
ans.push_back(j < n ? nums2[j] : -1);
}
return ans;
}
};func nextGreaterElement(nums1 []int, nums2 []int) []int {
n := len(nums2)
ans := make([]int, len(nums1))
for i, x := range nums1 {
j := 0
for nums2[j] != x {
j++
}
j++
for j < n && nums2[j] <= x {
j++
}
if j < n {
ans[i] = nums2[j]
} else {
ans[i] = -1
}
}
return ans
}var nextGreaterElement = function(nums1, nums2) {
return nums1.map(x => {
let j = nums2.indexOf(x) + 1;
while (j < nums2.length && nums2[j] <= x) j++;
return j < nums2.length ? nums2[j] : -1;
});
};function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
return nums1.map(x => {
let j = nums2.indexOf(x) + 1;
while (j < nums2.length && nums2[j] <= x) j++;
return j < nums2.length ? nums2[j] : -1;
});
}